Chess

Time Limit: 5000 ms Memory Limit: 65536 KiB

Problem Description

Chess is a two-player board game. There are some pieces in this game: king, queen, rook, knight, bishop and pawn.
Each chess piece has its own style of moving. In the diagrams, the dots mark the squares where the piece can move if no other pieces are on the squares between the piece's initial position and its destination. (We do not consider pawn)
 



- The king (K) moves one square in any direction. 
- The rook (R) can move any number of squares along any rank or file, but may not leap over other pieces.
- The bishop (B) can move any number of squares diagonally, but may not leap over other pieces.
- The queen (Q) combines the power of the rook and bishop and can move any number of squares along rank, file, or diagonal, but it may not leap over other pieces.
- The knight (N) moves to any of the closest squares that are not on the same rank, file, or diagonal, thus the move forms an "L"-shape, two squares vertically and one square horizontally or two squares horizontally and one square vertically. The knight is the only piece that can leap over other pieces.
There are n pieces in a chessboard. You know each piece's positions, the i-th piece is positioned in the square (ri, ci), there ri is the board row number and ci the board column number. No two pieces share the same position.
For each piece one can count w - the number of other pieces that attack the given piece. Obviously, for any piece w is between 0 and 16, inclusive.
Print the sequence t0, t1... t16, where ti is the number of pieces that each is attacked by exactly i other pieces, i.e. the number of pieces that their w equals i.

Input

The first line is a number T (1<=T<=50), represents the number of test cases. Then T blocks followed, each indicates a case.
The first line of each case contains an integers n (1 <= n <= 10^5), where n is the number of pieces on the board. The next n lines contain the positions and kinds of the pieces, one piece per line. Each line contains a pair of integers ri, ci (1 <= ri, ci <= 10^9) and the kinds ("KRBQN").

Output

Output the case number and the required sequence t0, t1... t16, separating the numbers with spaces. (As shown in the sample output)

Sample Input

2
5
3 3 N
1 2 N
2 1 N
4 5 N
5 4 N
5
3 3 Q
1 1 R
1 5 K
5 1 R
5 5 B

Sample Output

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

Hint

 

Source

2012年"浪潮杯"山东省第三届ACM大学生程序设计竞赛