There are N ninjas in a hidden ninja village. The main source of this village's income is the fees of the jobs completed by these N ninja. These N ninja follow a linear heirarchy. You are given the number of messages ninja i sends to ninja j during a mission. Your job is to output the hierarchy of these ninja which minimizes the number of messages sent from lower ranked ninjas to higher ranked ninjas. If multiple solutions are possible, return the lexicographically smallest solution.

Input Format The first line will contain the number of test cases T. T test cases will then follow.

For each test case, the first line will contain the number of ninjas N.

This will be followed by N lines. Each of these N lines will contain N integers each.

i'th number in line j denotes the number of messages sent by ninja j to ninja i.

Constraints

1 <= T <= 10

2 <= N <= 15

0 <= no. of messages from one ninja to another <= 9

Output Format Output T lines for T test cases. For each test case, output the ninjas in decreasing order of their ranks.