Cho một xâu \(s\). Cần thêm ít nhất bao nhiêu ký tự vào cuối xâu \(s\) để tạo thành một xâu đối xứng? In ra xâu đối xứng đó.

Input

• Dòng đầu tiên chứa một số nguyên dương \(t\), số truy vấn bạn phải trả lời \((1 \leq t \leq 100)\).
• \(t\) dòng tiếp theo, mỗi dòng chứa một xâu \(s\).
• Tổng độ dài các xâu \(s\) không vượt quá \(5 \times 10^5\).

Output

• Với mỗi truy vấn, in ra một dòng là xâu đối xứng tạo thành.

Example

4
aaaa
abba
amanaplanacanal
xyz 

aaaa
abba
amanaplanacanalpanama
xyzyx