Chiaki has a string ... w w^r w w^r ... with infinite length, where w=w₁w₂... w_m and w^r=w_m w_m-1 ... w₁.
Chiaki cuts out a substring s=s₁s₂... s_n (m < n) from the infinite string. And it's guaranteed s contains w or w^r as a substring. She would like to know the number of pairs (i,j) where 1 ≤ i ≤ j ≤ n and is a possible value of w or w^r.

输入描述:

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains a string s (2 ≤ |s| ≤ 106) consisting only of lowercase English letters.
It is guaranteed that the sum of |s| in all cases does not exceed 106.

输出描述:

For each test case, output an integer denoting the answer.

1
aaa

5