[Coding] 2-Letter Strings solution codeforces

Given nn strings, each of length 22, consisting of lowercase Latin alphabet letters from ‘a‘ to ‘k‘, output the number of pairs of indices (i,j)(i,j) such that i<ji<j and the ii-th string and the jj-th string differ in exactly one position.

In other words, count the number of pairs (i,j)(i,j) (i<ji<j) such that the ii-th string and the jj-th string have exactly one position pp (1p21≤p≤2) such that sipsjpsip≠sjp.

The answer may not fit into 32-bit integer type, so you should use 64-bit integers like long long in C++ to avoid integer overflow.

Input

The first line of the input contains a single integer tt (1t1001≤t≤100) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer nn (1n1051≤n≤105) — the number of strings.

Then follows nn lines, the ii-th of which containing a single string sisi of length 22, consisting of lowercase Latin letters from ‘a‘ to ‘k.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

[Coding] 2-Letter Strings solution codeforces

For each test case, print a single integer — the number of pairs (i,j)(i,j) (i<ji<j) such that the ii-th string and the jj-th string have exactly one position pp (1p21≤p≤2) such that sipsjpsip≠sjp.

Please note, that the answer for some test cases won’t fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

Example
input

Copy
4
6
ab
cb
db
aa
cc
ef
7
aa
bb
cc
ac
ca
bb
aa
4
kk
kk
ab
ab
5
jf
jf
jk
jk
jk

output

2-Letter Strings solution codeforces

Copy
5
6
0
6

Note

For the first test case the pairs that differ in exactly one position are: (“ab“, “cb“), (“ab“, “db“), (“ab“, “aa“), (“cb“, “db“) and (“cb“, “cc“).

For the second test case the pairs that differ in exactly one position are: (“aa“, “ac“), (“aa“, “ca“), (“cc“, “ac“), (“cc“, “ca“), (“ac“, “aa“) and (“ca“, “aa“).

For the third test case, the are no pairs satisfying the conditions.