tl3 | jaf (hard)

Mai sunt câteva minute până la întoarcerea miliardarului de la partida săptămânală de golf, iar Gigi și Gina (un fel de duo Bonnie și Clyde de România) i-au descoperit seiful. Din fericire, ei au de la menajeră o listă de posibile coduri. Cum miliardarul este un om foarte prudent și nu vrea ca cineva să îi rețină cifrul, folosește în tastarea lui doar cifrele $0$ și $1$ - reprezentarea binară a unui număr special. Astfel, codul final este unul foarte lung și aproape imposibil de memorat.

Totuși, Gigi și Gina mai au o informație valoroasă, care îi va ajuta să elimine dintre codurile posibile primite de la menajeră: numărul special este divizibil cu $3$.

Pentru a economisi timp, ei vor să încerce doar acele coduri care ar putea fi corecte (cum cifrul poate fi unul lung, tastarea fiecărui cod durează).

Cerință

Se citește un număr natural $T$, reprezentând numărul de teste care urmează. Pentru fiecare test se citește o valoare naturală $N$, numărul caracterelor din cod, iar apoi $N$ cifre de $0$ sau $1$. Scrieți un program care să decidă pentru un set de coduri primite dacă ar putea fi corecte (corespund codificării unui număr divizibil cu $3$).

Date de intrare

Fișierul de intrare jaf.in conține pe prima linie un număr natural $T$, reprezentând numărul testelor. Pe următoarele $T$ linii avem un număr natural $N$ și apoi $N$ cifre de $0$ sau $1$, separate prin câte un spațiu.

Date de ieșire

În fișierul jaf.out se va scrie pe linia $i$ mesajul DA, dacă al $i$-lea cifru primit poate fi unul corect sau NU, dacă acesta este greșit.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$
• $1 \leq T \leq 100$
• Șirul cifrelor poate începe cu mai multe cifre de 0.

Exemplu

jaf.in

5
6 1 0 0 1 0 0
8 1 0 1 0 1 0 0 1
7 0 0 1 1 0 0 0
4 1 0 1 0
7 1 0 0 0 1 0 0

jaf.out

DA
NU
DA
NU
NU

Explicație

$100100_{(2)}=36_{(10)}$ este multiplu de $3$
$10101001_{(2)}=169_{(10)}$ nu este multiplu de $3$
$0011000_{(2)}=24_{(10)}$ este multiplu de $3$
$1010_{(2)}=10_{(10)}$ nu este multiplu de $3$
$1000100_{(2)}=68_{(10)}$ nu este multiplu de $3$