Yêu cầu

Cho ~t~ truy vấn, mỗi truy vấn chứa một xâu ~s~ độ dài ~n~. Với mỗi truy vấn, hãy tìm số lượng kí tự ít nhất để thêm vào sau xâu ~s~ để tạo thành một palindrome.

Dữ liệu

• Dòng đầu tiên chứa số ~t~ - số truy vấn cần trả lời ~(1 \le t \le 100)~.
• Mỗi dòng trong ~t~ dòng tiếp theo chứa một xâu ~s~.
• Tổng độ dài các xâu không quá ~2 \times 10^5~.

Kết quả

• Với mỗi truy vấn, in ra trên cùng một dòng là số lượng kí tự ít nhất cần thêm vào và xâu ~s~ sau khi thêm những kí tự ấy.

Ví dụ

Sample Input

4
aaaa
educontest
xyz
abcdefghg

Sample Output

0 aaaa
9 educontestsetnocude
2 xyzyx
6 abcdefghgfedcba