Lộc và Tài tuy ở chung phòng nhưng hay gửi thư cho nhau. Mỗi bức thư chỉ có viết 1 từ duy nhất viết bằng các chữ cái tiếng Anh in thường, nhưng có độ dài rất lớn. Thực ra mỗi từ đó có chứa một thông điệp ẩn giấu mà phải người trong cuộc mới có thể tìm ra được: thông điệp là một xâu đối xứng dài nhất có thể có trong bức thư, được tạo thành từ việc xóa đi một số ký tự gây nhiễu liên tiếp nào đó (bản chất là ghép một phần đầu và một phần cuối của bức thư lại với nhau).

Bạn cùng phòng của Lộc và Tài vừa tìm ra được danh sách ~n~ bức thư của họ, họ cũng nghe trộm được cách truyền tải thông điệp giữa hai bạn nên muốn ngồi giải mã ra từng thông điệp đó xem có gì hot không. Hỏi độ dài của các thông điệp tìm được là bao nhiêu?

Input

Dòng đầu tiên gồm số nguyên dương ~t~ với ~1 \le t \le 10^5~ là số bức thư. Trong ~t~ dòng tiếp theo, mỗi dòng là một từ duy nhất.

Output

Với mỗi bức thư, cho biết độ dài của thông điệp tìm được.

Sample input

5
a
abcdfdcecba
abbaxyzyx
codeisfun
acbba

Sample output

1
9
5
1
4

Giải thích Trong bức thư thứ hai, thông điệp cần tìm là ~abcdfdcba~, còn trong bức thư thứ ba, thông điệp cần tìm là ~xyzyx~.

Subtasks

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

• Subtask 1 (50%): ~t≤1000,M≤5000~
• Subtask 2 (50%): ~t≤10^5,M≤10^6.~