exam-1

There are $Q$ questions on an exam, each with answer choices $A, B, C, D$. The correct answers are given as $H = h_1,\ldots,h_Q$. Correct answers are worth 1 point, wrong or missing answers are worth 0 points. Students’ answers are given as $a_1,\ldots,a_Q$. Some students have missing answers (denoted by ‘?’), and since the exam is about to end and there’s no penalty for wrong answers, they will answer these randomly. What is the expected value of the total score ($V$)?
For example, if there are Q=4 questions and N=3 students:

Correct answers: AACD
Student answers:
?AAB  ⟶  1×3/4 + 2×1/4  ⟶  expected 5/4 points
ABAB  ⟶  1  ⟶  expected 1 point
AA?A  ⟶  2×3/4 + 3×1/4  ⟶  expected 9/4 points
Thus V = 18/4 = 9/2 points is the expected total score.

Input specification

The first line contains $T$, the number of test cases. Description of each test case: First line: $Q$ (number of questions) and $N$ (number of students). Next line: string $H$ of correct answers. Then $N$ lines follow, each containing a string of length $Q$. The strings contain letters $A, B, C, D$ and ‘?’ (at most one ‘?’ per string).

Output specification

Output $T$ lines, each containing the corresponding $V$ for the test case, as a simplified fraction.

Constraints

$1\le T \le 100$
$1\le Q \le 5\_000$
$1\le N \le 100$

Sample input 1

1. 3
2. 4 3
3. AACD
4. ?AAB
5. ABAB
6. AA?A
7. 5 3
8. CCCCB
9. CCCCB
10. ?CCCA
11. CCAC?
12. 4 3
13. AACD
14. AAAB
15. ABAB
16. AAAA

Sample output 1

1. 9/2
2. 23/2
3. 5/1