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.

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.

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.

2010 ACM-ICPC Multi-University Training Contest（14）——Host by BJTU