Tiền tố và đối xứng

Tác giả:

Dạng bài

Điểm: 450 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

4
Qc93vcc11z
cSschccV2cccqZ
wccnq1c5gcqEK7mxc7cc
cccrc6cLCE

Output

Test 2

Input

5
tccPcq2Acc7mcs
7czY5SG8cGMccvQSQFnc
cccczsb1kgcySZcccicc
bDFckccfcrc
cccuHHcccccGcc

Output

Test 3

Input

2
abac
aa

Output

3
3

Note

Xét testcase \(3\):
Đối với xâu \("abac"\), ta sẽ có các tiền tố sau: \("a","ab","aba","abac"\). và "mức độ xinh đẹp" của chúng tương ứng là: \(A("a")=1,A("ab")=0,A("aba")=2,A("abac")=0\). Do đó tổng "mức độ xinh đẹp" của xâu đã cho là: \(1+0+2+0=3\)

Bình luận

1

duyboyct 11:30 a.m. 26 Tháng 11, 2021

Vì sao kết quả của truy vấn 4 Input 2 lại ra 6 vậy ad ?