Cho một xâu \(S\) chỉ bao gồm các ký tự số và chữ cái Latin. Gọi \(A(S)\) là "mức độ xinh đẹp" của xâu \(S\), và nó được định nghĩa theo công thức truy hồi như sau:

• \(A(S)=0\) nếu \(S\) là xâu không đối xứng hoặc là xâu rỗng

• Gọi \(n\) là độ dài của xâu \(S\), khi đó ta có: \(A(S)=k\) nếu tiền tố và hậu tố có độ dài là \(\left \lfloor{\frac{n}{2}}\right \rfloor\) của \(S\) đều có "mức độ xinh đẹp" là \(k-1\)

Yêu cầu:

• Cho xâu \(S\), hãy in ra tổng "mức độ xinh đẹp" của tất cả các tiền tố của xâu \(S\)

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa \(t\) xâu \(S(0\le |S|\le 10^5)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

4
Qc93vcc11z
cSschccV2cccqZ
wccnq1c5gcqEK7mxc7cc
cccrc6cLCE

1
1
1
5

5
tccPcq2Acc7mcs
7czY5SG8cGMccvQSQFnc
cccczsb1kgcySZcccicc
bDFckccfcrc
cccuHHcccccGcc

1
1
8
6
6

2
abac
aa

3
3