Similar License Plates

In the parking lot of the company where Albert works, n cars are parked in a row (from left to right). For convenience, number the cars 1 to n from left to right. Let x[i] be the string written on the license plate of car i. The n strings are distinct, and each is a string of length k consisting only of English letters (a-z and A-Z). That is, every license plate has the same length.

For any two cars i and j, if the plates x[i] and x[j] satisfy all of the following conditions, the two cars are said to have similar license plates:

• For each of the 26 letters, the number of times that letter appears in x[i] ignoring case equals the number of times it appears in x[j] (this condition must hold for every letter).
• The number of uppercase letters in x[i] equals the number of uppercase letters in x[j].

For example, let n = 4, k = 3, and x = ["AtY", "YtA", "aTy", "Ayt"].

• The plates of cars 1 and 2 are similar: both contain one A/a, one T/t, and one Y/y, and both have 2 uppercase letters out of 3.
• The plates of cars 3 and 4 are similar: both contain one A/a, one T/t, and one Y/y, and both have 1 uppercase letter out of 3.
• The plates of cars 1 and 3 are not similar: car 1 has 2 uppercase letters and car 3 has 1 (though the first condition holds).

Given n, k, and x[1], ..., x[n] as input, find the number of pairs of similar license plates and tell Albert.

The first line gives the number of test cases T.

The first line of each test case gives n and k separated by a space.

The second line gives n strings of length k separated by spaces.

Print the answer for each test case on its own line.

• 1 ≤ T ≤ 20
• 1 ≤ n ≤ 10,000
• 1 ≤ k ≤ 20