English

After obtaining secret data for his organization, Lam's task is now to attack Phong's system to avoid unexpected things happening, as well as to track Phong.

After sitting for a while calculating the network topology in Phong's system, Lam had the architecture of the server model that Phong built.

After modeling, the network architecture containing Phong's servers is represented by Lam on a square matrix of size N×N where N is the number of existing servers in Phong's system.

Between the i-th server and the j-th server with a direct connection, it will be represented on the matrix as a[i][j] = a[j][i] = 1. Otherwise, if there is no direct connection then the value at a[i][j] = a[j][i] = 0.

A server is said to be the weakest if, after this server is attacked, the entire network system will be divided into the most components.

Since there is not much time to attack all these servers, Lam wants to find the weakest server on the system to attack.

Case 1:

Case 2:

You are asked for help by Lam and your task this time is to be provided with a network model represented in the form of a matrix as described above, please help Lam find the server with the weakest position.

Input

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

The first line of each test case is a natural number N indicating the number of servers currently in the system (5 <= N <= 100.)

The next N lines, each of which are N values 0, 1 indicates the state at position a[i][j]. The status of the i-th server will be represented in the i-th line.

Example in case 1: Server 1 will have connection to servers 2, 3 and no connection to servers 4, 5. So the state of server 1 will be described as: 0 1 1 0 0.

Output

Each test case is printed on one line with the following format:

• Start with the character '#', followed by the ordinal number of that testcase, followed by a space, and finally the result of that test case.
• The result of the test case is an X number indicating the ID of the server that will be attacked. In the event that the attacked server cannot be found, X takes the value 0. If more than 1 server gives a weak result, then X takes the value of the ID of the smallest server in this list.

Example

Input:
2
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
5
0 1 1 0 0
1 0 1 0 1
1 1 0 1 1
0 0 1 0 1
0 1 1 1 0

Output:
#1 3
#2 0

Vietnamese

Sau khi đã có được dữ liệu bí mật phụ vụ cho tổ chức của mình, nhiệm vụ của Lâm giờ là phải tấn công hệ thống của Phong tránh những điều không mong muốn xảy ra, cũng như việc truy vết của Phong.

Sau một hồi ngồi tính toán Topo mạng trong hệ thống của Phong, Lâm đã có được kiến trúc của mô hình máy chủ mà Phong xây dựng.

Sau khi mô hình hóa, kiến trúc mạng chứa các máy chủ của Phong được Lâm biểu diễn trên một ma trận vuông kích thước N*N với N là số lượng máy chủ hiện có trong hệ thống của Phong.

Giữa máy chủ thứ i và máy chủ thứ j có kết nối trực tiếp sẽ được biểu diễn trên ma trận là a[i][j] = a[j][i] = 1. Ngược lại nếu không có kết nối trực tiếp thì giá trị tại a[i][j] = a[j][i] = 0.

Một máy chủ được gọi là xung yếu nhất nếu sau khi máy chủ này bị Tấn công thì toàn bộ hệ thống mạng sẽ phân chia thành nhiều thành phần nhất.

Do không có nhiều thời gian để tấn công tất cả các máy chủ này, nên Lâm muốn tìm máy chủ xung yếu nhất trên hệ thống để tấn công.

Case 1:

Case 2:

Bạn được Lâm nhờ giúp đỡ và nhiệm vụ lần này của bạn là đươc cung cấp mô hình mạng biểu diễn dưới dạng ma trận như mô tả trên, bạn hãy giúp Lâm tìm ra máy chủ có vị trí xung yếu nhất nhé.

Input

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

Dòng đầu tiên của mỗi testcase là số tự nhiên N cho biết số lượng máy chủ hiện có trong hệ thống (5 <= N <= 100)

N dòng tiếp theo, mỗi dòng là N giá trị 0, 1 cho biết trạng thái tại vị trí a[i][j]. Trạng thái của máy chủ thứ i sẽ được biểu diễn ở dòng thứ i.

VD trong case 1: Máy chủ 1 sẽ có kết nối đến các máy chủ 2, 3 và không có kết nối đến máy chủ 4, 5. Do đó trạng thái của máy chủ 1 sẽ được mô tả là: 0 1 1 0 0.

Output

Mỗi testcase được in trên một dòng với định dạng sau:

 - Bắt đầu bằng ký tự '#', tiếp theo là số thứ tự của testcase đó, theo sau là 1 dấu cách (khoảng trắng), và cuối cùng là kết quả của testcase đó.

 - Kết quả của testcase là 1 số X cho biết ID của máy chủ sẽ bị tấn công. Trong trường hợp không tìm ra máy chủ bị tấn công, X nhận giá trị là 0. Nếu có nhiều hơn 1 máy chủ cho kết quả xung yếu thì X nhận giá trị là ID của máy chủ nhỏ nhất trong danh sách này.

@tuantn18

Example

Input:
2
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
5
0 1 1 0 0
1 0 1 0 1
1 1 0 1 1
0 0 1 0 1
0 1 1 1 0

Output:
#1 3
#2 0