타자 치는 원숭이

타자기를 다룰 줄 아는 원숭이를 구했다. 이 원숭이는 정해진 확률분포에 따라 영어 소문자를 한 글자씩 끝없이 입력하고, 키를 누르는 사건은 서로 독립이다.

당신은 이 원숭이가 언젠가 셰익스피어 전집을 그대로 쳐낼 것이라고 믿는다. 친구는 해리 포터 시리즈의 새 소설을 써낼 가능성이 더 크다고 본다. 어느 쪽이 먼저인지 가리려고, 두 작품을 각각 한 단어로 줄여 놓고 한 단어가 다른 단어보다 먼저 나올 확률을 계산하기로 했다.

원숭이가 지금까지 친 글자열 안에 어떤 단어가 부분 문자열로 나타나면, 그 순간 원숭이가 그 단어를 만들어 냈다고 한다. 두 단어 $P$와 $Q$가 주어질 때, 원숭이가 $Q$보다 $P$를 먼저 만들어 낼 확률을 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스는 두 줄이다. 첫째 줄에는 원숭이가 a부터 z까지 각 글자를 칠 확률 $p_a, p_b, \ldots, p_z$가 이 순서대로 공백 하나씩으로 구분되어 주어진다. 둘째 줄에는 두 문자열 $P$와 $Q$가 공백 하나로 구분되어 주어진다. 두 문자열은 영어 소문자로만 이루어진다.

• $0 < T \le 100$
• $0 \le p_\alpha \le 1$이고 $\sum_\alpha p_\alpha = 1$
• $0 < |P|, |Q| \le 16$
• $P$와 $Q$는 서로 다르다.
• $P$나 $Q$에 등장하는 글자의 확률은 모두 0보다 크다.
• 원숭이가 $P$와 $Q$를 같은 시점에 완성하는 입력은 주어지지 않는다.

각 테스트 케이스마다 원숭이가 $Q$보다 $P$를 먼저 만들어 낼 확률을 한 줄에 하나씩 출력한다. 소수점 아래 일곱째 자리에서 반올림하여, 소수점 아래 여섯 자리를 항상 채워서 출력한다.