CrackContest | B - Al doilea Crack

Cerință

Șmenul lui Aquilla ne ajută să rezolvăm următoarea problemă:

Dacă avem o tablă de șah $N$-dimensională, adică avem doar casuțe de culori albe și negre și nu există $2$ căsuțe de aceași culoare adiacente, iar în fiecare căsuță este un cărăbuș cu o anumita orientare (daca $N=2$, aceasta poate fi: sus, jos, stânga, dreapta, deci se poate muta către o căsuță adiacentă).

Putem alege o orientare a cărăbușilor astfel încât dacă se mută toți deodată să nu se ajungă cu $2$ sau mai mulți cărăbuși pe aceași căsuță (orientarea trebuia aleasă ca cărăbușii să nu iasă de pe tablă)?
Să se răspundă la $T$ teste.

Date de intrare

Pe prima linie se află $T$, urmat de $T$ linii, pe fiecare se află câte un $N$.

Date de ieșire

Se cer $N$ rânduri, răspunsul poate fii DA sau NU.

Restricții și precizări

• $1 \leq T \leq 10^5$;
• $2 \leq N \leq 10^5$;
• Atenție, răspusul este DA sau NU, nu YES sau NO :)
• O tablă de șah $N$ dimensională are si laturile de lungime $N$. (O tablă $5$ dimensională este de $5 \times 5 \times 5 \times 5 \times 5$).
• Să fie si mai clar, de exemplu într-o tablă $3$ dimensională un cărăbuș se poate mișca: sus, jos, față, spate, stânga, dreapta. Iar pentru $N=4$ sunt $8$ direcții de mișcare.

Exemplul 1

stdin

1
2

stdout

DA

Explicație

$T=1$.
Avem o tablă de $2 \times 2$.
Orientările pot fi alese:
Cărăbușul de pe $(1,1)$ se mută jos.
Cărăbușul de pe $(1,2)$ se mută stânga.
Cărăbușul de pe $(2,1)$ se mută dreapta.
Cărăbușul de pe $(2,2)$ se mută sus.
Carăbușii se mișcă simulta, după ce se mișcă nu va exista o căsuță cu $2$ sau mai mulți cărăbuși.

Exemplul 2

stdin

2
3
16

stdout

NU
DA

Explicație

Tabla este un cub de $3 \times 3 \times 3$, se poate demonstra că nu există soluție.
Tabla este un cub de $16 \times 16 \times 16 \times 16 \times 16$..., există o soluție.