English

The substring of string S is defined as a string consisting of consecutive characters (>=2 characters) of string S. Your task is a bit more difficult than in PROB16. Now that you are given an initial string S, your task is to write a program to find the palindromic substring with the longest length.

Input

The first line is the number of test cases T of the problem (1 <= T <= 100).

The next T lines, each of which is a string S with a maximum length of 10,000 characters.

Output

Each test case is printed on one line with: starting with a '#' character, followed by the test case's number, followed by a space, and finally the result of that test case.

Format of the result:

• If a palindromic substring is found: length of the substring, and the substring itself.
• If a palindromic substring cannot be found: -1.

See example output to understand more.

Example

Input:
3
ABC
AABCBA
ABCDCBAA

Output:
#1 -1
#2 5 ABCBA
#3 7 ABCDCBA

Vietnamese

Chuỗi con của chuỗi S được định nghĩa là chuỗi bao gồm các ký tự liên tiếp nhau (>=2 ký tự) của chuỗi S. Nhiệm vụ của bạn khó khăn một chút so với bài PROB16. Bây giờ bạn được cho một chuỗi S ban đầu, nhiệm vụ của bạn là viết một chương trình tìm chuỗi con đối xứng có độ dài lớn nhất.

Input

Dòng đầu tiên là số testcase T của bài toán (1 <= T <= 100)

T dòng tiếp theo, mỗi dòng là một chuỗi S có độ dài tối đa 10.000 ký tự

Output

Mỗi testcase được in trên một dòng với: bắt đầu bằng ký tự '#', tiếp theo là số thứ tự của testcase đó, tiếp theo là 1 dấu cách (khoảng trắng),và cuối cùng là kết quả của testcase đó.

Format của kết quả:

- Nếu tìm được chuỗi con đối xứng: Len Substring

- Nếu không tìm được chuỗi con đối xứng: -1

Xem example output để hiểu thêm

Example

Input:
3
ABC
AABCBA
ABCDCBAA

Output:
#1 -1
#2 5 ABCBA
#3 7 ABCDCBA