Given a matrix $A$ with $N$ rows and $M$ columns, it is guaranteed to satisfy the following properties:

1. $M > N$.
2. Each number in the matrix is a natural number in $[0, N]$.
3. In each row, every natural number in $[1, N]$ appears exactly once. This means that $0$ appears exactly $M - N$ times in each row.
4. In each column, every natural number in $[1, N]$ appears at most once.

Now we want to select a non-zero number in each row and set all numbers following it in that row to this value. We want to maintain property 4 above, that is, in each column, every natural number in $[1, N]$ still appears at most once.

Input

The first line contains a positive integer $T$, representing the number of test cases.

Following are $T$ test cases, with no empty lines between them. Each test case starts with two positive integers $N$ and $M$, followed by $N$ rows, each containing $M$ space-separated integers, as described above.

Output

For each test case, output one line. If a solution exists, output $N$ integers, representing the number chosen for each row in order. (This should be a permutation of $1$ to $N$). If no solution exists, output any cute emoticon.

Examples

input

2
5 10
0 1 0 2 3 0 0 4 0 5
2 0 3 0 0 1 0 5 4 0
4 2 1 0 0 0 3 0 5 0
0 3 0 4 0 5 0 1 2 0
1 0 0 3 2 4 5 0 0 0
5 10
0 1 0 2 3 0 0 4 0 5
2 0 3 0 0 1 0 5 4 0
4 2 1 0 0 0 3 0 5 0
0 3 0 4 0 5 0 1 2 0
1 0 0 3 2 4 5 0 0 0

output

4 5 3 1 2
5 4 3 1 2

Note

The two sets of input data are identical. Since the result is not unique, you can provide any valid set of answers.

Constraints

For 20% of the data, $M < 8, T < 8$.

For 40% of the data, $N < 8, T < 8$.

For 100% of the data, $N < 200, M < 400, T < 50$.

Cute emoticons include but are not limited to "\(^o^)/" (without quotes).

Due to the large size of the input data, please optimize your input method.