Gra w kulki

Limit pamięci: 128 MB

Bajtek i Bitek postanowili zagrać w kulki. W urnie znajduje się parzysta liczba kulek. Na każdej z nich zapisana jest dokładnie jedna cyfra. Zasady gry są bardzo proste: gracze na przemian wyjmują z urny po jednej, losowo wybranej kulce. Gra kończy się, gdy w urnie nie ma już żadnych kulek. Wygrywa gracz, który zgromadził zestaw kulek o większym iloczynie cyfr.

Chłopcy bardzo polubili tę grę. Obaj są bardzo ambitni i naprawdę lubią wygrywać, więc jedyną sytuacją końcową, która nie zadowala żadnego z nich, jest remis. Bajtek i Bitek chcieliby za wszelką cenę uniknąć takich rozstrzygnięć. Napisz program, który sprawdzi, czy dla zadanej początkowej zawartości urny gra może zakończyć się remisem.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę przypadków testowych do rozważenia.

Każdy z kolejnych wierszy zawiera po dziesięć nieujemnych liczb całkowitych (), gdzie oznacza liczbę kulek, na których zapisana jest cyfra . Suma liczb w każdym przypadku testowym jest parzysta i dodatnia.

Wyjście

Twój program powinien wypisać wierszy z odpowiedziami dla poszczególnych przypadków testowych. Odpowiedzią dla jednego przypadku testowego jest słowo TAK, jeśli rozważana gra może zakończyć się remisem, lub NIE, w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

5
0 1 0 1 1 4 1 0 5 1
0 1 1 0 3 0 0 0 0 3
1 1 0 4 0 0 2 0 0 2
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 999999 999999 1000000 1000000 1000000 1000000 1000000 1000000 1000000

poprawną odpowiedzią jest:

TAK
NIE
NIE
TAK
NIE

Autor zadania: Jakub Radoszewski