시험

많은 대학이 학생이 최대 100점을 받을 수 있는 채점 방식을 사용한다. 이 중 최대 75점은 학기 중에, 최대 25점은 기말고사에서 얻는다. 최종 학점은 학기 점수와 시험 점수의 합에 따라 아래 표대로 정해진다.

학기 중에 35점 미만을 받은 학생은 시험에 응시할 수 없으며, 그런 학생은 이미 명단에서 제외되었다고 가정한다. 따라서 명단에 있는 모든 학생의 학기 점수는 35점 이상이다.

명단의 유럽식 학점 열을 위에서 아래로 읽으면 알파벳으로 이루어진 문자열, 즉 "단어"가 만들어진다. 예를 들어 연속한 세 학생의 점수 합계가 각각 92, 75, 66이면 학점은 A, C, E가 되어 단어 ACE를 이룬다. 학점이 FX이면 두 글자, 먼저 F 그다음 X가 기여한다.

시험 결과는 미리 알 수 없지만, 강사는 각 학생의 수준과 출제 목록을 알고 있어, 모든 학생에 대해 그 학생이 시험에서 정확히 0, 1, 2, …, 25점을 받을 확률(백분율)을 추정할 수 있다. 이는 합이 100인 26개의 음이 아닌 정수다. 각 학생의 학기 점수는 확률 없이 고정된 값(35 이상 75 이하의 정수)으로 주어진다.

강사는 심미주의자여서, 유럽식 학점으로 만들어진 단어가 어떤 "불쾌한" 문자열을 (연속한) 부분 문자열로 포함하는 상황을 싫어한다.

불쾌한 문자열의 집합이 주어질 때, 단어가 그 어느 것도 부분 문자열로 포함하지 않아 강사가 만족할 확률을 구하라.

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

각 테스트 케이스는 학생 수 $N$ ($3 \le N \le 100$)이 적힌 줄로 시작한다. 이어지는 $N$개의 줄에는 각각 한 학생이 공백으로 구분된 27개의 정수로 주어진다. 먼저 그 학생의 학기 점수(35 이상 75 이하의 정수), 그다음 그 학생이 시험에서 $0, 1, 2, \ldots, 25$점을 받을 확률을 나타내는 26개의 백분율이 온다. 각 백분율은 음이 아닌 정수이며, 26개의 합은 100이다.

그다음 줄에는 불쾌한 단어의 수 $K$ ($1 \le K \le 100$)가 주어진다. 이어지는 $K$개의 줄에는 각각 불쾌한 단어가 하나씩 주어지며, 대문자 라틴 문자로만 이루어진다(A–F와 X뿐 아니라 임의의 대문자). 각 단어의 길이는 2 이상 15 이하다.

각 테스트 케이스마다, 강사가 만족할 확률(백분율), 즉 단어가 불쾌한 부분 문자열을 하나도 포함하지 않을 확률을 한 줄에 출력한다.

이 확률을 기약 분수 p/q 형태로 정확히 출력한다. 분자와 분모는 슬래시 /로 구분하고, 분수는 기약 상태이며, 분모는 양수다. 확률이 0이면 0/1로, 정수 $v$ 퍼센트이면 v/1로 출력한다(예: 100%는 100/1).

첫 번째 예제를 살펴보자. 첫 번째 학생은 $p_0 = \cdots = p_9 = 0$이므로 시험에서 최소 10점을 받아 총점이 최소 $72 + 10 = 82$이다. 따라서 이 학생의 학점은 항상 A 또는 B이고 절대 D가 아니다. 그러므로 불쾌한 단어 DE는 두 번째와 세 번째 학생에게서만 나올 수 있다. 이는 두 번째 학생의 학점이 D(시험 13–19점, 확률 $8 + 8 + 7 + 6 + 5 + 4 + 3 = 41\%$)이고 세 번째 학생의 학점이 E(시험 5–12점, 확률 $3 + 4 + 5 + 6 + 7 + 8 + 8 + 9 = 50\%$)일 때 정확히 나타난다. 따라서 DE가 나타날 확률은 $0.41 \times 0.50 = 0.205$이고, 나타나지 않을 확률은 $1 - 0.205 = 0.795$, 즉 $79.5\%$이다. 기약 분수로는 159/2이다.