Rooks

You are given a square board of size $n \times n$ in which some cells have been removed. You want to place $n$ rooks on the remaining cells so that all of the following rules hold:

• a rook may be placed only on a cell that has not been removed;
• each cell holds at most one rook;
• no two rooks attack each other, that is, every row and every column contains exactly one rook.

The number of valid placements can be enormous. For example, if no cell has been removed, the rooks can be arranged in $n!$ ways. Your task is simpler: you only need to decide whether the number of valid placements is even or odd.

Write a program that reads the description of the boards and reports $0$ when the number of rook placements is even, or $1$ when it is odd.

The first line contains a single integer $t$, the number of boards ($1 \le t \le 10$). The $t$ board descriptions follow.

Each board description starts with a line containing a single integer $n$, the size of the board ($1 \le n \le 250$). The next $n$ lines describe the rows of the board in order. Each such line contains $n$ integers from the set $\{0, 1\}$ separated by single spaces, where $0$ means the cell has been removed and $1$ means a rook may be placed on that cell.

Print $t$ integers, one per line. On the $i$-th line print $0$ if the number of rook placements for the $i$-th board is even, or $1$ if it is odd.

The illustration above shows every valid rook placement on one sample board of size $3 \times 3$.