guess-the-permutation-1

Lucifer is having a permutation of integers from 1 to N denoted by P. Let i^th element of P be denoted as Pi. For all pairs of distinct integers i and j between 1 to N, he wrote the number ai,j = min(pi, pj). He writes ai,i = 0.

Given all values of ai,j, Lucifer wants you to find permutation P.
 
Input 
First line contains integer T(number of test cases) 
Next line contains integer N.
Next N lines will contain the values ai,j. j^th number on i^th line denotes ai,j.The i^th number on the  i^th line will be 0. It's guaranteed that ai,j = aj,i and there is at least one solution consistent with the information given.

Output

If there are multiple solutions for the given input, print the permutation which is lexicographical smallest.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 1000

SAMPLE INPUT
2
2
0 1
1 0
5
0 2 2 1 2
2 0 4 1 3
2 4 0 1 3
1 1 1 0 1
2 3 3 1 0

SAMPLE OUTPUT
1 2
2 4 5 1 3

Source: hackerearth | Difficulty: EASY


Solutions: