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:
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.
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.
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.
2 2 HELLOWORLD LIPPSASVPH 5 ACM CEO HUST IVTU JWUV
Case #1: 1 Case #2: 4