VIP - VIP

no tags 

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


Added by:Rafał Witkowski
Date:2022-03-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:It was presented by Piotr Zieliński to watch candidate ability to participate in programming cotenst