sudoku

Sudoku este un joc care se desfășoară pe o tablă pătratică formată din $9$ linii și $9$ coloane. În fiecare dintre celule trebuie scrisă o valoare cuprinsă între $1$ și $9$. De regulă se dau o parte dintre valorile din celule iar pe restul trebuie să le completăm noi astfel încât:

• Pe fiecare linie să apară exact o dată orice număr de la $1$ la $9$
• Pe fiecare coloană să apară exact o dată orice număr de la $1$ la $9$
• În fiecare dintre cele $9$ submatrice pătratice $3 \times 3$ (evidențiate în exemplul de mai jos) să se afle fiecare număr de la $1$ la $9$.

Cerință

În această problemă nu avem de completat vreo tablă, ci ni se dau table deja completate și noi trebuie să decidem dacă acestea sunt corecte, conform regulilor jocului, enunțate mai sus.

Date de intrare

Fișierul de intrare sudoku.in conține pe prima linie o valoare $N$, reprezentând numărul de table de joc pentru care trebuie să facem verificarea.
Mai departe sunt $N$ matrice $9 \times 9$. Fiecare este dată prin $9$ linii cu câte $9$ valori pe fiecare, separate prin spațiu. Între oricare două matrice este un rând liber.

Date de ieșire

Fișierul de ieșire sudoku.out conține, pe un singur rând, $N$ valori care pot fi $1$ și $0$ și neseparate prin spații.
Pentru o tablă, în ordinea din fișierul de intrare, se va scrie $1$ dacă ea este corect completată și $0$ în caz contrar.

Restricții și precizări

• $2 \leq N \leq 20$
• Valorile din matrice sunt numere naturale cuprinse între $1$ și $9$.

Exemplu

sudoku.in

2
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9

6 8 2 1 9 4 3 5 7
7 3 1 5 6 8 9 2 4
4 9 5 7 2 3 8 6 1
8 2 7 9 3 5 1 4 6
5 1 9 6 4 7 2 8 3
3 6 4 2 8 1 5 7 9
9 5 6 4 1 2 7 3 8
2 4 8 3 7 9 6 1 5
1 7 3 8 5 6 4 9 2

sudoku.out

01