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^5 and
digits only between 0 and 9 both inclusive.

Output

Number of pairs of such digits.

Example

Input:

2
1234
777

Output:

4
9