Find the transitive closure of a given directed graph (digraph). The digraph is given in the form of an adjacency matrix and the transitive closure of the graph is expected in the matrix form.

Input

The input begins with the number t of test cases in a single line (t <= 100). Each test case begins with number of vertices n of the digraph in a new line (1 <= n <= 100) and the following n lines with the adjacency matrix of the graph. An entry at row i and column j in the adjacency matrix is 1 if there is an edge from vertex i to vertex j in the graph, otherwise 0.

Output

For every test case print the matrix representing the transitive closure of the graph. An entry at row i and column j in the matrix should be 1 if there is a path from vertex i to vertex j in the graph, otherwise 0. A matrix of order n should be printed in n lines each line having n entries of a row of the matrix.

Example

Input:
4
2
0 0
0 0
2
0 1
1 0
4
0 1 0 0
0 0 0 1
0 0 0 0
1 0 1 0
1
1

Output:
0 0
0 0
1 1
1 1
1 1 1 1
1 1 1 1
0 0 0 0
1 1 1 1
1