Any string can be "hashed" into some sequence of characters or integers. However, before we start hashing, let us define a simple procedure that can be operated on a string, called folding the string:
- First, add a
y
to the end of the string if the string has an odd length. - Take the first and last character of string and convert each of them to a number between and . If the character is
a
, it becomes the integer1
,b
becomes2
, etc. - Then, multiply these two integers together. If their value is greater than , continually subtract until the value is between and (inclusive). Convert this new integer back into a letter between
a
andz
(1
=a
,2
=b
, etc.). - This letter becomes the first character of the new string.
- Continue performing steps and until the new string is fully created, using the second and second last character, third and third last, etc. The new string should be exactly half the length of the old string. (including the changes performed in step ).
- The string has been folded.
As an example, we will walk through the process of folding bbc
:
- The string has an odd length, so we add a
y
, giving usbbcy
. - The first character is
b
, which becomes . The last character isy
, which becomes . - When we multiply the two integers together, we get . Since this number is larger than , we continually subtract . This gives us , which becomes the letter
x
. - The first letter of the new string is now
x
. - Performing steps and on the second and second last character gives us the character
f
. The string at this point isxf
. - The string has been fully folded, so the final string after folding
bbc
isxf
.
One possible (though not very practical) way of "hashing" a string into one character consists of a series of steps:
- If the length of the string is exactly , the string has been successfully hashed, and we can exit.
- Otherwise, fold the string, and goto step .
This one character string is the hash of the original string.
You are given strings, and you want to compute the hash of each one. Notice that the final hash of the string can only be a single character between a
and z
, which is subpar. Thus, you are curious as to how many pairs of strings have the same hash. Can you print this information out?
Input Specification
The first line will contain the integer , the number of strings.
The next lines will each contain a string for which you are to hash. Each string will only consist of lowercase latin characters. It is guaranteed the sum of the string lengths of all strings does not exceed .
Output Specification
On the first line, output the number of pairs of the strings that have the same hash.
Subtasks
Subtask 1 [10%]
and each string will have a length of at most .
Subtask 2 [40%]
Subtask 3 [50%]
No further constraints.
Sample Input
4
abcd
no
hello
ninjaclasher
Sample Output
1
Explanation
By performing the "hashing":
abcd
becomesx
no
becomesb
hello
becomesb
ninjaclasher
becomesn
Only no
and hello
have the same hash, so there is only one pair. Thus, the answer outputted is 1
.
Comments