Untitled

Sau khi biết tin Eagle xây dựng hệ thống điện và ăn bớt được rất nhiều kinh phí, VenG rất tức vì khi anh xây cầu anh đã không ăn bớt được đồng nào. Do đó anh quyết phá hệ thống điện của Eagle.

Do sợ bị phát hiện nên anh sẽ chỉ phá hệ thống điện ở trên 1 hòn đào, và anh muốn tìm hòn đảo nào sau khi phá xong thì hệ thống điện của Eagle bị chia cắt thành nhiều phần nhất.

Hãy giúp anh VenG tìm hòn đảo này.

Input:

Dòng đầu tiên ghi số bộ test, không lớn hơn 100.

Mỗi bộ test được tổ chức theo khuôn dạng sau:

 Dòng đầu tiên ghi lại số tự nhiên N không lớn hơn 100 là số hòn đảo.

Những dòng kế tiếp ghi lại ma trận biểu diễn hệ thong mạng lưới điện, trong đó 0 được hiểu là không có đường dây điện nối giữa điểm i và j, 1 được hiểu có đường dây điện trực tiếp giữa điểm i và điểm j (1<=i, j <= N).

Output

Với mỗi bộ test, in ra màn hình trên một dòng một số duy nhất là hòn đảo bị phá hủy hệ thống điện thỏa mãn yêu cầu bài toán (nếu có nhiều đảo cùng thỏa mãn yêu cầu thì in ra đảo có giá trị nhỏ nhất). Nếu không thể chia cắt được hệ thống điện, hãy in ra số 0.

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:

3

0



5
10
0	1	1	1	0	0	0	0	0	0
1	0	1	0	0	0	1	0	0	0
1	1	0	1	0	1	0	0	0	0
1	0	1	0	1	0	0	0	0	0
0	0	0	1	0	1	0	0	0	1
0	0	1	0	1	0	1	0	1	0
0	1	0	0	0	1	0	1	0	0
0	0	0	0	0	0	1	0	1	0
0	0	0	0	0	1	0	1	0	1
0	0	0	0	1	0	0	0	1	0
10
0	1	1	1	0	0	0	0	0	0
1	0	0	0	0	0	1	0	0	0
1	0	0	0	0	1	0	0	0	0
1	0	0	0	1	0	0	0	0	0
0	0	0	1	0	0	0	0	0	1
0	0	1	0	0	0	0	0	1	0
0	1	0	0	0	0	0	1	0	0
0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	1	0	0	0	0
0	0	0	0	1	0	0	0	0	0
15
0	1	1	1	0	0	0	0	0	0	0	0	0	0	0
1	0	1	0	0	0	1	0	0	0	0	0	0	0	0
1	1	0	1	0	1	0	0	0	0	0	0	0	0	0
1	0	1	0	1	0	0	0	0	0	0	0	0	0	0
0	0	0	1	0	1	0	0	0	1	0	0	0	0	0
0	0	1	0	1	0	1	0	1	0	0	0	0	0	0
0	1	0	0	0	1	0	1	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0	0	0	1	1	0	0	1
0	0	0	0	0	1	0	0	0	1	0	0	1	0	0
0	0	0	0	1	0	0	0	1	0	0	0	0	1	0
0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	1	0	0	0	0	1	0
0	0	0	0	0	0	0	0	0	1	0	0	1	0	0
0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
15
0	1	0	0	1	0	1	0	0	0	0	0	0	0	0
1	0	1	0	1	0	0	0	0	0	0	0	0	0	0
0	1	0	1	0	0	0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0	1	1	0	0	1
1	1	0	0	0	1	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	1	0	0	0	0	0	0
1	0	0	0	1	0	0	1	0	0	0	0	0	0	0
0	0	0	0	0	0	1	0	0	1	0	0	0	0	0
0	0	0	0	0	1	0	0	0	0	0	0	1	0	0
0	0	0	0	0	0	0	1	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	1	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0	0	0	0	0	0
15
0	1	0	0	1	0	1	0	0	0	0	0	0	0	0
1	0	1	0	1	0	0	0	0	0	0	0	0	0	0
0	1	0	1	0	1	0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	1	0	1	1	0	0	1
1	1	0	0	0	1	1	0	0	0	0	0	0	0	0
0	0	1	0	1	0	0	1	1	0	0	0	0	0	0
1	0	0	0	1	0	0	1	0	0	0	0	0	0	0
0	0	0	0	0	1	1	0	0	1	0	0	0	0	0
0	0	0	1	0	1	0	0	0	1	0	0	1	0	0
0	0	0	0	0	0	0	1	1	0	0	0	0	1	0
0	0	0	1	0	0	0	0	0	0	0	1	0	0	1
0	0	0	1	0	0	0	0	0	0	1	0	1	0	0
0	0	0	0	0	0	0	0	1	0	0	1	0	1	0
0	0	0	0	0	0	0	0	0	1	0	0	1	0	0
0	0	0	1	0	0	0	0	0	0	1	0	0	0	0   


import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

// 100: BFS
public class Ans {
	public static void main(String[] args)  {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {

		}
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T+2; tc++) {
			if(sc.hasNextInt()){
				N = sc.nextInt();
				arr = new int[N][N];
				
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						arr[i][j] = sc.nextInt();
					}
				}
				
				int tempArr[][] = backUp();
				
				int max = 2;
				answer = 0;
				for (int i = 0; i < N; i++) {
					
					for (int j = i; j < N; j++) {
						
						if (tempArr[i][j] == 1) {
							tempArr[i][j] = 0;
							tempArr[j][i] = 0;
						}
					}
					if (demSoVung(tempArr) > max) {
						max = demSoVung(tempArr);
						answer = i + 1;
					}
					tempArr = backUp();
					
				}
				
				System.out.println(answer);
			}
		}

	}

	private static int[][] backUp() {
		int tempArr[][] = new int[N][N];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempArr[i][j] = arr[i][j];
		return tempArr;
	}

	private static int demSoVung(int tempArr[][]) {
		int soVung = 0;
		visited = new boolean[N];
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				BFS(i, tempArr);
				soVung++;
			}
		}
		return soVung;
	}

	static int N;
	static int arr[][];
	static int answer;
	static boolean visited[];

	static void BFS(int start, int tempArr[][]) {
		MyQueue q = new MyQueue(N);
		visited[start] = true;
		q.add(start);

		while (!q.isEmpty()) {
			int v = q.remove();

			for (int i = 0; i < N; i++) {
				if (tempArr[v][i] == 1 && !visited[i]) {
					visited[i] = true;
					q.add(i);
				}
			}
		}
	}

	static class MyQueue {
		int front, rear;
		int arr[];

		public MyQueue(int size) {
			arr = new int[size];
			rear = front = -1;
		}

		public void add(int item) {
			rear++;
			arr[rear] = item;
		}

		public int remove() {
			return arr[++front];
		}

		public boolean isEmpty() {
			return front == rear;
		}
	}

}