Forest University (Small)

Forest University offers $N$ courses, and a student must take all of them to obtain a degree. Courses are taken one at a time: a student must complete a course before starting another. Each course is either basic or advanced. A basic course can be taken without any prior knowledge. An advanced course has exactly one other course as its prerequisite.

A student must take the prerequisite of a course before the course itself, although the two do not need to be taken one right after the other. A course can be the prerequisite of several other courses. The prerequisites contain no cycles. Every order of the $N$ courses that respects the prerequisites is valid for obtaining the degree.

At graduation, the university prints an abbreviated version of the student's course order on the graduation hat. This abbreviation is the string formed by the first letter of the name of each course, in the order the courses were taken. For example, a student who took a Coding course and then a Jamming course gets a hat that says CJ. Having certain cool words as a substring of the string on one's hat is considered trendy.

Consider all valid course orders. For each cool word, find the fraction of valid course orders whose hat string contains that cool word as a substring at least once. The fraction is taken over course orders, not over distinct hat strings. Several courses can share the same first letter, so there may be fewer distinct strings than course orders.

Each valid course order is counted once, so the answer is an exact rational number. Print it as an irreducible fraction.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case consists of the following five lines, in this order.

1. The number of courses $N$.
2. $N$ integers. The $i$-th integer is the number of the prerequisite of the $i$-th course, or 0 if the $i$-th course is basic. The courses are numbered from 1 to $N$.
3. $N$ uppercase English letters with no whitespace in between. The $i$-th letter is the first letter of the name of the $i$-th course.
4. The number of cool words $M$.
5. $M$ cool words separated by spaces. Each word consists of uppercase English letters only.

Limits

• $1 \le T \le 100$
• $1 \le N \le 12$
• $1 \le M \le 5$
• The length of each cool word is between 1 and 20, inclusive.
• Each cool word consists of uppercase English letters only.
• The prerequisites form no cycles.

For each test case, print one line in the form Case #x: y1 y2 ... yM, where x is the test case number starting from 1 and yi is the fraction of valid course orders whose hat string contains the $i$-th cool word as a substring.

Print each yi as an irreducible fraction p/q with $q \ge 1$ and $\gcd(p, q) = 1$. A fraction equal to 0 is printed as 0/1, and a fraction equal to 1 is printed as 1/1.

In the first test case of the sample, course 1 (C) is a basic course and the prerequisite of the advanced course 2 (J). The only way to complete the courses is to take course 1 and then course 2, which gives the string CJ. The cool words CJ, C, D, and JC appear as substrings in 1, 1, 0, and 0 of the 1 possible order, so the answer is 1/1 1/1 0/1 0/1.

In the second test case, the basic course 1 (B) is the prerequisite of the advanced course 2 (A), and course 3 (A) is another basic course. There are three ways to complete the courses.

1. Course 1, then course 2, then course 3 (string BAA).
2. Course 1, then course 3, then course 2 (string BAA).
3. Course 3, then course 1, then course 2 (string ABA).

The cool words AA, AAB, and ABA appear in 2, 0, and 1 of the 3 possible orders, so the answer is 2/3 0/1 1/3.