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 đếm xem trong chuỗi đó có bao nhiêu chuỗi con là chuỗi đối xứng.
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 trong input là số test case. Mỗi test case được viết trên một dòng duy nhất, là chuỗi đầu bài cho.

Output

In ra 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 2
#2 6