There are $N$ players playing a guessing game. Each player guesses a sequence consists of $\{1, 2, 3, 4, 5, 6\}$ with length $L$, then a dice will be rolled again and again and the roll out sequence will be recorded. The player whose guessing sequence first matches the last $L$ rolls of the dice wins the game.

Input

The first line is the number of test cases. For each test case, the first line contains 2 integers $N$ ($1 \le N \le 10$) and $L$ ($1 \le L \le 10$). Each of the following $N$ lines contains a guessing sequence with length $L$. It is guaranteed that the guessing sequences are consists of $\{1, 2, 3, 4, 5, 6\}$ and all the guessing sequences are distinct.

Output

For each test case, output a line containing the winning probability of each player with the precision of 6 digits.

Sample Input

3
5 1
1
2
3
4
5
6 2
1 1
2 1
3 1
4 1
5 1
6 1
4 3
1 2 3
2 3 4
3 4 5
4 5 6

Sample Output

0.200000 0.200000 0.200000 0.200000 0.200000
0.027778 0.194444 0.194444 0.194444 0.194444 0.194444
0.285337 0.237781 0.237781 0.239102