Cho một xâu kí tự ~S~ chỉ chứa các kí tự viết thường trong bảng chữ cái Tiếng Anh. Hãy tìm xâu ~T~ có độ dài lớn nhất thỏa mãn cái điều kiện sau:

• ~T~ có độ dài không vượt quá độ dài của ~S~

• ~T~ là một xâu đối xứng (hay Palindrome, cách đọc từ trái sang phải giống cách đọc từ phải sang trái)

• Tồn tại ~2~ xâu ~a, b~ (có thể rỗng) sao cho ~T = a + b~ (với dấu ~+~ có ý nghĩa là phép gộp xâu) và ~a~ là một tiền tố của xâu ~S~, ~b~ là một hậu tố của xâu ~S~.

Hãy in ra độ dài xâu ~T~.

Input

• Dòng ~1~: Chứa số nguyên dương ~t~ ~(1 \le t \le 10^5)~ là số bộ dữ liệu trong test này.

• Dòng đầu tiên trong mỗi bộ dữ liệu gồm một xâu kí tự ~S~.

Output

• In ra ~t~ dòng tương ứng là độ dài xâu ~T~ tìm được của mỗi bộ dữ liệu.

Scoring

Gọi ~M~ là tổng độ dài tất cả các xâu ~S~ trong mỗi test.

Sample Input 1

5
a
abcdfdcecba
abbaxyzyx
codeisfun
acbba

Sample Output 1

1
9
5
1
4

Notes

• Trong bộ dữ liệu đầu tiên, xâu ~T~ cũng chính là xâu ~S~.

• Trong bộ dữ liệu thứ hai, xâu ~T =~ "abcdfdcba" ~=~ "abcdfdc" ~+~ "ba" với "abcdfdc" là một tiền tố của xâu ~S~, còn "ba" là một hậu tố của xâu ~S~.

• Trong bộ dữ liệu thứ ba, xâu ~T =~ "xyzyx" ~=~ "" ~+~ "xyzyx", trong đó ~a =~ "" còn ~b =~ "xyzyz".