Efficient Algotithms 2022

One day there was a party in the town. A VIP was invited to the party - a person that is known by everyone in the town, while he himself does not know anyone.
Write a computer program that finds the VIP in a crowd of people.

Input

The first line of the input contains one integer d (1 <= d <= 100), which indicates the number of data sets.
Each set consists of several lines. The first line contains a natural number n (1 <= n <= 500), which indicates the number of people present at the event. The next n lines each contain n numbers 0 or 1. Such a number in the i-th row and j-th column means:

• 0 - i-th person does not know j-th person,
• 1 - i-th person knows j-th person.

Each person knows himself.
We know that VIP exists, i.e., there is a person whom is known by everyone and who knows no one but himself

Output

Output one number for each data set, meaning the number of the person who is a VIP.

Example

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

Output:
3
4