POLSKI SPOJ

Napisz program, który będzie sprawdzać czy podana tabela 9x9 liczb całkowitych jest prawidłowym rozwiązaniem łamigłówki sudoku.

Wejście

W pierwszej linii - jedna liczba całkowita n określająca liczbę przypadków testowych. Następnie kolejne przypadki testowe, w każdym 9 linii po 9 liczb całkowitych z przedziału <-1000, 1000> oddzielonych spacjami. Przypadki testowe są rozdzielone pustą linią.

Wyjście

Dla każdego przypadku testowego w wejściu jedna linia zawierająca słowo "TAK" lub "NIE" w zależności od tego, czy dany zestaw danych stanowi poprawne rozwiązanie sudoku.

Przykład

Wejście:
5
2 5 1 7 6 9 3 4 8
9 8 6 3 4 5 2 7 1
3 7 4 8 2 1 6 9 5
4 2 9 6 3 8 5 1 7
8 6 3 5 1 7 9 2 4
5 1 7 4 9 2 8 3 6
7 9 5 1 8 3 4 6 2
1 4 2 9 5 6 7 8 3
6 3 8 2 7 4 1 5 9

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

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

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

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

Wyjście:
TAK
NIE
TAK
NIE
NIE