Problem Description

Apple is a very careless girl. One day, the teacher leaves her a problem which has stuck her for a long while. Apple turns to you with this problem: counting the number of the isosceles right triangles composed with various letters in a capital letters matrix. And there are only two forms of the isosceles right triangle in the matrix:
Form 1:
Two right sides are both parallel with the sides of the matrix. e.g.

Form 2:
The hypotenuse is parallel with one side of the matrix. e.g.


Notice that all the isosceles right triangles should contain more than or equal to three letters.

Input

The first line of the input file contains a single integer t ( 1 ≤ t ≤ 20 ), the number of test cases, followed by the input data for each test case. The first line of each test case consists of one integer K ( 1 ≤ K ≤ 50). K is the size of matrix. The follow K lines, each lines has K capital letters, describe a K*K character matrix. There is no space both at the beginning and the end of all the lines.

Output

For each collection, output "Case k:", where k is the number of the test case. To every letter appeared in the matrix, it is required to count the number of the isosceles and right triangles in the matrix composed with it. Moreover, the output should be arrayed in the nature order of these letters in a dictionary. A blank should be left between the letter and its corresponding number. We confirm that the result are less than 2^31.

2 
3 
AAB 
ABB 
BBC 
4 
AABB
ABBB 
BBBB
BBBB

Case 1: 
A 1 
B 3 
C 0 
Case 2: 
A 1 
B 50

Author

Seraf