Cho một bàn cờ vuông kích thước ~N \times N~, trên đó có một số ô cấm. Bạn cần đặt ~N~ quân xe lên đấy sao cho:

• Trên mỗi ô của bàn cờ, chỉ có tối đa ~1~ quân xe
• Không có quân xe nào được đặt lên các ô cấm
• Không có ~2~ quân xe nào có thể ăn được nhau (cùng hàng hoặc cùng cột). Chú ý rằng các quân xe có thể đi xuyên qua ô cấm.

Đếm số cách đặt ~N~ quân xe lên bảng, theo modulo ~2~ (mod ~2~).

Input

• Dòng ~1~: Số nguyên dương ~T~ - số bộ test.

• Tiếp theo là ~T~ bộ test, mỗi bộ test gồm:

  • Dòng ~1~: Số nguyên dương ~N~
  • Tiếp theo là ~N~ dòng, dòng thứ ~i~ gồm ~N~ số nguyên. Số nguyên thứ ~j~ trên dòng ~i~ là ~0~ nếu ô tương ứng là ô cấm và bằng ~1~ trong trường hợp ngược lại.

Output

Gồm ~T~ dòng, mỗi dòng là một số nguyên duy nhất là số cách đặt quân xe theo modulo ~2~.

Giới hạn

• ~1 \leq T \leq 10~
• ~1 \leq N \leq 250~
• Trong 20% số test, ~N \leq 15~

Sample Input

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

Sample Output

1
1

Note

• Trong test đầu tiên, có ~3~ cách xếp. Bạn cần in ra ~3 \bmod 2 = 1~
• Trong test thứ hai, có duy nhất ~1~ cách xếp. Bạn cần in ra ~1 \bmod 2 = 1~