숲 대학교 (Small)

숲 대학교에는 $N$개의 과목이 있고, 학위를 받으려면 모든 과목을 수강해야 한다. 과목은 한 번에 하나씩만 들을 수 있으며 한 과목을 마쳐야 다음 과목을 시작할 수 있다. 각 과목은 기초 과목이거나 심화 과목이다. 기초 과목은 선수 지식 없이 들을 수 있고, 심화 과목에는 선수 과목이 정확히 하나 있다.

어떤 과목을 들으려면 먼저 그 과목의 선수 과목을 들어야 한다. 단, 두 과목을 연달아 들을 필요는 없다. 한 과목이 여러 과목의 선수 과목일 수도 있다. 선수 과목 관계에는 사이클이 없다. 선수 과목 규칙을 지키는 $N$개 과목의 수강 순서는 모두 학위 취득에 유효하다.

졸업할 때 대학교는 학생의 수강 순서를 줄여서 졸업 모자에 인쇄한다. 줄인 문자열은 수강한 순서대로 각 과목 이름의 첫 글자를 이어 붙인 것이다. 예를 들어 Coding 과목과 Jamming 과목을 이 순서로 들었다면 졸업 모자에는 CJ가 적힌다. 졸업 모자의 문자열에 몇몇 멋진 단어가 부분 문자열로 들어 있으면 유행에 맞는다고 여긴다.

가능한 모든 유효한 수강 순서를 생각하자. 각 멋진 단어마다 졸업 모자 문자열에 그 단어가 부분 문자열로 한 번 이상 나타나는 수강 순서의 비율을 구하라. 비율은 서로 다른 졸업 모자 문자열의 개수가 아니라 수강 순서의 개수로 계산한다. 여러 과목의 첫 글자가 같을 수 있으므로 가능한 문자열의 수는 수강 순서의 수보다 적을 수 있다.

유효한 수강 순서는 각각 한 번씩 세므로 답은 정확한 유리수이다. 답은 기약분수로 출력한다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 다음 다섯 줄로 이루어진다.

1. 과목의 수 $N$.
2. $N$개의 정수. $i$번째 정수는 $i$번째 과목의 선수 과목 번호이고, $i$번째 과목이 기초 과목이면 0이다. 과목 번호는 1부터 $N$까지이다.
3. 공백 없이 이어진 $N$개의 영어 대문자. $i$번째 문자는 $i$번째 과목 이름의 첫 글자이다.
4. 멋진 단어의 수 $M$.
5. 공백으로 구분된 $M$개의 멋진 단어. 각 단어는 영어 대문자로만 이루어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 12$
• $1 \le M \le 5$
• 각 멋진 단어의 길이는 1 이상 20 이하이다.
• 각 멋진 단어는 영어 대문자로만 이루어진다.
• 선수 과목 관계에는 사이클이 없다.

각 테스트 케이스마다 Case #x: y1 y2 ... yM 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, yi는 졸업 모자 문자열에 $i$번째 멋진 단어가 부분 문자열로 들어 있는 유효한 수강 순서의 비율이다.

각 yi는 기약분수 p/q로 출력한다. 이때 $q \ge 1$이고 $\gcd(p, q) = 1$이다. 비율이 0이면 0/1, 1이면 1/1로 출력한다.

예제의 첫 번째 테스트 케이스에서 과목 1(C)은 기초 과목이며 심화 과목 2(J)의 선수 과목이다. 과목을 모두 듣는 방법은 과목 1 다음에 과목 2를 듣는 것 하나뿐이고, 이때 문자열은 CJ이다. 따라서 멋진 단어 CJ, C, D, JC는 가능한 순서 1개 중 각각 1개, 1개, 0개, 0개에 부분 문자열로 나타나며 답은 1/1 1/1 0/1 0/1이다.

두 번째 테스트 케이스에서 기초 과목 1(B)은 심화 과목 2(A)의 선수 과목이고, 과목 3(A)은 또 다른 기초 과목이다. 과목을 모두 듣는 방법은 세 가지이다.

1. 과목 1, 과목 2, 과목 3 순서 (문자열 BAA)
2. 과목 1, 과목 3, 과목 2 순서 (문자열 BAA)
3. 과목 3, 과목 1, 과목 2 순서 (문자열 ABA)

멋진 단어 AA, AAB, ABA는 가능한 순서 3개 중 각각 2개, 0개, 1개에 나타나므로 답은 2/3 0/1 1/3이다.