Young Dope was bored of finding whether a given number is palindromic or not. So he started another exercise described as follows. Given a number consisting of n digits, find the number of pairs of digits such that position[i] equals position[j] (1 ≤ i, j ≤ n).

Input

First line contains T, the number of test cases < 100.

Each test case contains a number with 1 ≤ length ≤ 10⁵ and digits only between 0 and 9 both inclusive.

Output

Number of pairs of such digits.

Example

Input:
2
1234
777

Output:
4
9