Giải bài trực tuyến

Cho một bàn cờ vuông kích thước N*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 ≤ T ≤ 10
• 1 ≤ N ≤ 250
• Trong 20% số test, N ≤ 15

Chấm điểm

• Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.
• Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.
• Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.

Example

Input:
2
3
1 0 1
0 1 1
1 1 1
2
1 0
0 1

Output:
1
1

Giải thích

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