Xâu Palind

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à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$.

Yêu cầu: Hãy in ra độ dài xâu $T$.

Dữ liệu vào

• 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.
• Mỗi bộ dữ liệu gồm một dòng chứa một xâu kí tự $S$ khác rỗng.

Dữ liệu ra

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

Ràng buộc

• $1\le t\le {10}^5$.
• Gọi $M$ là tổng độ dài tất cả các xâu $S$ trong mỗi test: $M\le {10}^6$.
• $S$ chỉ gồm chữ cái tiếng Anh in thường.

Subtasks

• Subtask 1 ($50\%$ số điểm): $t\le 1000$, $M\le 5000$.
• Subtask 2 ($50\%$ số điểm): $t\le {10}^5$, $M\le {10}^6$.

Mỗi subtask được chấm theo nhóm: chỉ được điểm của subtask khi đúng mọi test thuộc subtask đó.

Ví dụ