There are N participants in a chess competition. They are given unique ids, numbered from 1 to N. Every participant will play against every other participant in a game. Thus there will be (N*(N-1))/2 games in total. Assume none of the games result in a draw.

 

A sponsor wants to meet all the players. But he can do so only one by one and in the following manner-

 

1. He can choose to meet any player at first.
2. After meeting a player i, the next player he meets, say j, should be such that i defeated j.

 

Help him decide an order such that he is able to meet all the players.
If there are multiple such orders, output the lexicographically smallest one.
The games are such that if a defeats b, and b defeats c, then a defeats c.
He doesn't want to meet any player more than once.

 

Input

 

1. First line contains integer t, the number of test cases.
2. For each test case, first line contains integer N.
3. Next N lines contain a string of 0 and 1 of length N, such that, if jth character of i^th line is 1, then i defeated j, otherwise j defeated i.

 

Output

 

For each test case, output in a single line the required order.

 

 

Constraints

 

1T
1N

 

Examples

Input
3
3
011
000
010
2
0
1
4
0010
1010
0000
1110
Output
1 3 2
2 1
4 2 1 3