Sherlock and Anagrammatic Pairs

Given a string \(S\), find the number of unordered pairs of substrings \((a, b)\) such that:

• The substrings are of equal length.
• The substrings are taken from different positions in \(S\).
• The two substrings are anagrams of each other.

For any group of identical substrings (after sorting), the number of pairs is computed using the formula $$\frac{n(n-1)}{2},$$ where \(n\) is the number of occurrences of that particular sorted substring. Your task is to calculate this number for each string provided.

Example: For \(S = \texttt{abba}\), the answer is 4.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
S1
S2
... 
ST

Here, the first line contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains a string \(S\).

outputFormat

For each test case, output the number of anagrammatic pairs found in the string. Each answer should be printed on a new line to standard output (stdout).

## sample

1
abba

4

</p>