Chiaki has a string s. She would like to know the number of (i,j) (1 ≤ i < j ≤ |s|) such that: after swapping si and sj, s can be represented as concatenation of two palindromes.
Note that a string is called palindrome if and only if its characters read the same backward as forward.
输入描述:
There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:
The first line contains a string s (1 ≤ |s| ≤ 105)consisting of lowercase English letters.
It is guaranteed that the sum of all |s| does not exceed 106.
输出描述:
For each test case, output an integer denoting the answer.