你得到了一只猴子，它会使用打字机，甚至能够按照特定的概率分布敲击字母。

你相信这只猴子最终能够打出莎士比亚的全集。然而，你的朋友 Eirik 认为，这只猴子更有可能写出《哈利·波特》系列中的另一部小说。

为了解决这个分歧，你需要编写一个程序，计算猴子在打出另一段文字之前先打出某段特定文字的概率，这里用单词来表示。如果一个单词在猴子敲击出的字母流中作为子串出现，则称该单词被产生。猴子只能敲击英文小写字母。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例包含两行。第一行包含 26 个浮点数 $p_a, p_b, \dots, p_z$，表示猴子敲击每个字母的概率，每个概率之间用空格分隔。第二行包含两个字符串 $P$ 和 $Q$，中间用空格分隔。两个字符串均由英文小写字母组成。这两个字符串永远不会相等，且猴子能够产生这两个字符串的概率始终大于零。不存在猴子能同时产生这两个字符串的测试用例。

输出格式

对于每个测试用例，输出猴子在产生单词 $Q$ 之前产生单词 $P$ 的概率。

数据范围

• $0 < T \leq 100$
• $0 \leq p_{\alpha} \leq 1$
• $\sum p_{\alpha} = 1$
• $0 < |P|, |Q| \leq 16$
• 与正确答案的绝对误差或相对误差不超过 $10^{-7}$ 即可被接受。
• 猴子的按键是独立事件。

样例

输入 1

1
0.1 0 0 0 0.1 0 0 0.1 0 0 0 0.1 0.1 0 0.1 0.1 0 0.1 0 0.2 0 0 0 0 0 0
hamlet potter

输出 1

0.33333333333333