Given the nodes and adjacency matrix of a graph, calculate the adjacency list for it.

You have a graph with n nodes indexed from 0 to n-1. You also have the adjacency matrix where each cell denotes whether two nodes are connected.

You have to return the adjacency list for the given graph.

Example

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has the following lines:

• The first line contains the integer n.
• The next n lines contain n space-separated integers each denoting the adjacency matrix.

Output Format

For each test case, the output has n lines denoting the adjacency list of the graph.

Sample Input

2
4
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
4
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 1

Expected Output

1 2 3
0
0 3
0 2
1 2 3
0
0 3
0 2 3

Constraints

1 <= T <= 10
1 <= n <= 500