Palindrome tiền tố + hậu tố

Cho 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 thỏa mãn đồng thời các điều kiện sau:

• Độ dài của $t$ không vượt quá độ dài của $s$.
• $t$ là một xâu palindrome (đọc xuôi và đọc ngược giống nhau).
• Tồn tại hai xâu $a$ và $b$ (có thể rỗng) sao cho $t=a+b$, trong đó $a$ là tiền tố của $s$ và $b$ là hậu tố của $s$.

Nếu có nhiều xâu $t$ thỏa mãn cùng độ dài lớn nhất, in ra bất kỳ xâu nào.

Dữ liệu vào

Dòng đầu chứa số nguyên $T$ ($1\le T\le 1000$) — số lượng test.

Mỗi test gồm một dòng duy nhất chứa xâu $s$ không rỗng, gồm các chữ cái latin in thường.

Tổng độ dài của tất cả $s$ trong một bộ test không vượt quá $5000$.

Dữ liệu ra

Với mỗi test, in ra một dòng chứa xâu $t$ dài nhất thỏa mãn các điều kiện trên.

Ví dụ