In Byteland after the food shortage banks made credit payment freely available. At the end of the year companies have to settle their debts and to give a statement on their cashflow to the Claim Office. Among Banks and Companies a net of debts was created. Unfortunetely Banks gave a sky-high price on money transfers. For company owners it was unprofitable to pay all money transfers as they were. They chose you to help them out. Your assignment is to balance the debt network.

You are given [t<=1000] test cases- a test case consists of the size [N<=1000] of the debt network, followed by a description of the network itself. Each line consists of integers separated by spaces ending with a new line. Each value states how much money the company in line "i" is in debt to company "j" where "j" is the column number.

Your assignment is to limit the number of money transfers by determining which companies are in debt, which have earned money and which have shown neither profit nor loss.

Input

t [- test cases]
N [- size of the debt net]
a[1,1] a[1,2] a[1,3] ... a[1,n]
a[2,1] a[2,2] a[2,3] ... a[2,n]
...[[debt size for each company - a[1,3] denotes the sum borrowed by company 1 from 3]]
...
a[n,1] a[n,2] a[n,3] ... a[n,n]
[empty line]
[next test case]

a graphical example

Output

T[Size of solution]
a[1,1] a[1,2] a[1,3] ... a[1,n]
a[2,1] a[2,2] a[2,3] ... a[2,n]
...[[debt size for each company - a[1,3] denotes the sum borrowed by company 1 from 3]]
...
a[n,1] a[n,2] a[n,3] ... a[n,n]
[empty line]
[next solution]

[All the output data should be integers.]
Text grouped in [ ] does not appear in the input file.

a graphical example



a graphical example- same input

Example

Input:
1
7
0 18 25 34 14 21 40 
44 0 64 0 11 5 24 
11 35 0 23 17 26 23 
19 50 20 0 16 7 0 
0 14 9 0 0 27 18 
42 5 17 8 3 0 17 
36 26 0 47 7 6 0 


Output:
7
0 10 0 0 0 0 0 
0 0 0 0 0 0 0 
0 12 0 0 0 6 3 
0 0 0 0 0 0 59 
0 0 0 0 0 0 29 
0 0 0 0 0 0 0 
0 0 0 0 0 0 0