Description

$N$ people have been gathered to compete in the Rock-Paper-Scissors contest. Every two players will play a match against each other, that is, each player will play against $N-1$ different opponents.

One match of Rock-Paper-Scissors consists of 10 rounds, each round the two players will play either Rock, Paper or Scissors.

We know that Paper defeats Rock, Scissors defeats Paper, and Rock defeats Scissors.

We also know the sequence each player will play by every match.

Now we wish to know for every person, the number of people will he win 0 rounds, the number of people he will win 1 round, ... the number of people he will win 10 rounds.

For example, if the first person plays by the sequence RRSSSPPPPP, and the second person plays by the sequence RRRRRRRRRR.

The first person will win $5$ of the matches, while the second person will win $3$ of the matches.

Input

First line is the number of test cases $T (T \leq 5)$.

For each test case, first line will be an integer $N (2 \leq N \leq 30000).$

Then follow N lines, each line consists of $10$ characters, one of R/P/S.

R - stands for Rock.

P - stands for Paper.

S - stands for Scissors.

Output

For each test case, first output “Case #x:”, where x is the test case number (starting from $1$).

Then output N lines, each consists of $11$ integers: the number of people that the ith person can win $0$ matches, $1$ match, $2$ matches ... $10$ matches.

Sample Input

2
4
RRRRRRRRRR
SSSSSSSSSS
PPPPPPPPPP
RRSSSPPPPP
6
RRRRPPPRPP
PSRSPPPPSP
RSPPRSSRRP
SPPRSRRRSS
RPPSPRSSSS
RSRRSPRSSP

Sample Output

Case #1:
1 0 0 1 0 0 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 1
1 0 1 0 0 0 0 0 0 0 1
0 0 1 1 0 1 0 0 0 0 0
Case #2:
0 0 1 4 0 0 0 0 0 0 0
0 0 1 2 2 0 0 0 0 0 0
0 0 0 1 2 1 1 0 0 0 0
0 0 0 2 1 2 0 0 0 0 0
0 1 1 0 2 1 0 0 0 0 0
0 1 1 2 0 1 0 0 0 0 0