Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 15
Solved: 3
Description

 


    In ancient Rome, people develop an encryption technique called Caesar Cipher. A Caesar Cipher is an Alphabetic table as followed. To encrypt a Cipher-text, every character in the Plain-text will be replaced by a corresponding char. A Plain table is just an Alphabet, while a Cipher table removes the first k char and add it on the back of table e.g. every character will be replaced by the k-th character on its right. Notice that there is no character after ‘Z’, so we treat the Alphabet as a circle and define the next one as ‘A’. Here is an example as k=4:


 


       Plain:    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z


       Cipher:   E F G H I J K L M N O P Q R S T U V W X Y Z A B C D


 


       And here is a simple conversion example:


       Plain-text:  HELLOWORLD


       Cipher-text: LIPPSASVPH


       Further more, we define a pair of two texts a “relevant pair” if one can be converted from another using this Cipher technique. For example, “HELLOWORLD” and “LIPPSASVPH” is a relevant pair, “ACM” and “BCD” isn’t. Give you a set of test including only UPPER-CASE CHARACTER and your task is to calculate how many pair of “relevant pair” can be found in the set.


 


 

Input

 


  The first line of the contains a single integer T - the number of test cases.


  In the first line of each case there is one integer n - the number of text.(1<=n<=10000)


  Then follow n lines, each line contain a text Li. You may assume the length of each L will not exceed 100.


 

Output

 


  For each test case, first output”Case #i: ”,where i refers to the number of cases and a space is expected after’:’, then output the number of “relevant pair”, each answer occupies a line.


 


 

sample input
2
2
HELLOWORLD
LIPPSASVPH
5
ACM
CEO
HUST
IVTU
JWUV
sample output
Case #1: 1
Case #2: 4
hint
<p><span lang="EN-US"><span style="font-family: Simsun; font-size: medium;">Huge amount of input. Using scanf instead of std::cin to get faster IO.</span></span> </p> <p style="margin: 0cm 0cm 0pt;"><span lang="EN-US"><span style="font-family: Simsun; font-size: medium;">For the second case, the four pairs are:</span></span></p> <p style="margin: 0cm 0cm 0pt;"><span lang="EN-US"><span style="font-family: Simsun; font-size: medium;">ACM --- CEO</span></span></p> <p style="margin: 0cm 0cm 0pt;"><span lang="EN-US"><span style="font-family: Simsun; font-size: medium;">HUST ---IVTU</span></span></p> <p style="margin: 0cm 0cm 0pt;"><span lang="EN-US"><span style="font-family: Simsun; font-size: medium;">IVTU ---JWUV</span></span></p> <p style="margin: 0cm 0cm 0pt;"><span lang="EN-US"><span style="font-family: Simsun; font-size: medium;">HUST ---JWUV</span></span></p> <p style="margin: 0cm 0cm 0pt;"> </p>
source
songwenhao
Submit