### Fight Club

Time Limit: 1000 ms
Memory Limit: 65536 KiB

#### Problem Description

Fight club is an organization where you release your pressure and emotion by fighting the other club members. The fight begins like this: n people standing in a circle. Then two adjacent guys are chosen to fight. The winner will stay and the loser will be sent to the hospital(there is no tie in the fighting). The cruel fight continues until there is only one left.

It is somewhat strange to see that when two guys fight each other, the result is always definite, and you know the result of every pair of fighters. Thouth they enjoy fighting, they still want to be the winner. You are to tell each of them, if the fight is arranged properly, can he be the winner.

It is somewhat strange to see that when two guys fight each other, the result is always definite, and you know the result of every pair of fighters. Thouth they enjoy fighting, they still want to be the winner. You are to tell each of them, if the fight is arranged properly, can he be the winner.

#### Input

First line contains integer T(T<=5), the number of test cases.

For each test case, the first line contains n(1<=n<=40), the number of people. Following is the description of a n*n matrix A. Following n lines each contains n '0' or '1', separeted by a single blank. The i

For each test case, the first line contains n(1<=n<=40), the number of people. Following is the description of a n*n matrix A. Following n lines each contains n '0' or '1', separeted by a single blank. The i

^{th}number in j^{th}line indicates the fighting result of i^{th}and j^{th}fighter. If it is '1', then the i^{th}fighter will always beat the j^{th}fighter, otherwise he will always lose. You can safely assume that a_{ij}and a_{ji}are different and a_{ii}=0 for every distinct i and j. The people are numbered counterclockwise.#### Output

For each test case, output n lines. If the i

Output a blank line after each test case.

^{th}fighter can be the survivor, output 1, otherwise output 0.Output a blank line after each test case.

#### Sample Input

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

#### Sample Output

1 0 1 0 0