English

In PROB17 you are given only one initial sequence and must find the longest palindromic substring. Now that you are given a character matrix, your task is to check rows and columns to find the substring with the largest length. If both rows and columns produce palindromic substrings of equal length, the results of the row traversal are preferred.

Input

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

The first line of each test case is a natural number N indicating the size of the matrix (5 <= N <= 1000).

Next N lines, each containing N characters

Output

Each test case is printed on one line with: starting with the character '#', followed by the test case 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:
1
7
CDCCBDB
DCCDDDD
BACBCBB
BBADBCD
DABADAA
BACDDBB
DACDBBA

Output:
#1 5 DABAD

Vietnamese

Ở bài PROB17 bạn chỉ được cho một chuỗi ban đầu và phải tìm chuỗi con đối xứng dài nhất. Giờ đây bạn được cho một matrix ký tự, nhiệm vụ của bạn là đi kiểm tra theo hàng, cột để tìm ra chuỗi con có độ dài lớn nhất. Nếu cả dòng và cột cùng ra chuỗi con đối xứng có độ dài bằng nhau thì ưu tiên kết quả duyệt theo dòng.

Input

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

Dòng đầu tiên của mỗi testcase là số tự nhiên N cho biết kích thước của matrix (5 <= N <= 1000)

N dòng tiếp theo, mỗi dòng chứa N ký tự

Output

Mỗi testcase được in ra trên 1 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à một dầu cách (khoảng trắng), và cuối cùng là kết qủa của testcase đó.

Format của kết quả:

- Nếu tìm được chuỗi con đối xứng dài nhất: 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:
1
7
CDCCBDB
DCCDDDD
BACBCBB
BBADBCD
DABADAA
BACDDBB
DACDBBA

Output:
#1 5 DABAD