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ác điều kiện sau:

• \(t\) có dộ 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 ghép xâu \(b\) vào sau xâu \(a\)) 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\).

Yêu cầu: Hãy in ra độ dài xâu \(t\).

Dữ liệu vào:

+ Dòng đầu chứa số nguyên \(tc\ (1 \leq tc \leq 10^{5})\) là số bộ dữ liệu trong test;

+ \(tc\) dòng tiếp theo, mỗi dòng ghi một xâu kí tự \(s\).

Kết quả:

+ Ghi ra \(tc\) dòng tương ứng là độ dài xâu \(t\) tìm được của mỗi bộ dữ liệu.

Ví dụ:

Ràng buộc:

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

+ Có 50% số test tương ứng 50% số điểm có \(t \leq 1000;M \leq 5000\);

+ Có 50% số test còn lại tương ứng 50% số điểm có \(t \leq 10^{5},M \leq 10^{6}\).