COETEST5

Cho 1 chuỗi có độ dài tối đa là 1000 ký tự viết thường
Viết chương trình in ra độ dài của chuỗi con đối xứng dài nhất
Chuỗi đối xứng là chuỗi khi đọc từ trái sang phải hay từ phải sang trái đều như nhau

Input

Dòng đầu tiên của input là số test case. Mỗi test case được viết trên một dòng duy nhất, chứa chuỗi đầu bài cho.

Output

In kết quả theo định dạng sau: đầu tiên là kí tự "#", tiếp theo là số thứ tự của test case, tiếp theo là khoảng trắng (dấu cách) và cuối cùng là kết quả.

Example

Input:
2
ab
aaa

Output:
#1 1
#2 3