Rock Paper Scissors

Time Limit: 2000 ms Memory Limit: 524288 KiB

Problem 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 <= 5)

For each test case, first line will be an integer N. (2 <= N <= 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

Hint

Source

“浪潮杯”山东省第七届ACM大学生程序设计竞赛