Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMROOK - Xe

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmrook


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

Được gửi lên bởi:VOJ Team
Ngày:2013-07-15
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.