Xâu đối xứng tiền tố - hậu tố

Cho một xâu $s$ gồm các chữ cái Latin in thường. Hãy tìm xâu $t$ dài nhất thoả mãn đồng thời ba điều kiện sau:

• Độ dài của $t$ không vượt quá độ dài của $s$.
• $t$ là xâu đối xứng, tức là $t$ đọc từ trái sang phải và từ phải sang trái đều như nhau.
• Tồn tại hai xâu $a$ và $b$ (có thể rỗng) sao cho $t=a+b$ (dấu $+$ là phép ghép xâu), trong đó $a$ là một tiền tố của $s$ và $b$ là một hậu tố của $s$.

Lưu ý rằng $a$ và $b$ được lấy độc lập với nhau: chúng có thể chồng lấn lên nhau trên $s$, thậm chí một trong hai (hoặc cả hai) có thể rỗng.

Chương trình cần xử lý nhiều bộ dữ liệu trong cùng một tệp vào.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $T$ là số bộ dữ liệu.
• $T$ dòng tiếp theo, mỗi dòng chứa một xâu $s$ không rỗng gồm các chữ cái Latin in thường.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng xâu $t$ dài nhất thoả mãn các điều kiện trên. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $1\le T\le {10}^5$
• Tổng độ dài của tất cả các xâu $s$ không vượt quá ${10}^6$.

Ví dụ