== include(page="template/taskheader" task_id="ubercool") ==

Cu totii stim ca Balul Bobocilor al Facultăţii de Matematică şi Infomatică din Universitatea din Bucureşti este peste doua zile si e ultima sansa pentru un student ca IWD sa o scoata in oras pe IWM. Cum IWM este studenta la matematica, si IWD cauta sa o impresioneze, el s-a gandit la urmatoarea problema: Fiind dat un numar $X$, poate el sa spuna daca acesta este ubercool? Un numar este ubercool daca este de forma $a^b^$, unde $a$ este un numar prim si $b ≥ 2$. Deoarece IWD are prea multe emotii, va roaga pe voi sa ii dati solutia.

Cu toţii ştim ca Balul Bobocilor al Facultăţii de Matematică şi Informatică din Universitatea din Bucureşti este peste doua zile şi e ultima şansă pentru un student ca IWD sa o scoată în oraş pe IWM. Cum IWM este studenta la matematica, şi IWD cauta sa o impresioneze, el s-a gândit la următoarea problema: Fiind dat un număr $X$, poate el sa spună dacă acesta este ubercool? Un număr este ubercool dacă este de forma $a^b^$, unde $a$ este un număr prim şi $b ≥ 2$. Deoarece IWD are prea multe emoţii, va roagă pe voi sa ii daţi soluţia.

h2. Date de intrare

Fişierul de intrare $ubercool.in$ contine pe prima linie $T$, numarul de teste, iar apoi pe linia $i+1$, $1 ≤ i ≤ T$, se afla un numar $X$.

Fişierul de intrare $ubercool.in$ conţine pe prima linie $T$, numărul de teste, iar apoi pe linia $i+1$, $1 ≤ i ≤ T$, se afla un număr $X$.

h2. Date de ieşire

Fişierul de ieşire $ubercool.out$ contine $T$ linii. Pe linia $i$, $1 ≤ i ≤ T$, $"DA"$ daca numarul $X$ de pe linia $i+1$ din input este ubercool, $"NU"$ altfel.

Fişierul de ieşire $ubercool.out$ conţine $T$ linii. Pe linia $i$, $1 ≤ i ≤ T$, $"DA"$ dacă numărul $X$ de pe linia $i+1$ din input este ubercool, $"NU"$ altfel.

h2. Restricţii si precizari

h2. Restricţii şi precizări

* $1 ≤ T ≤ 5.000$

* $1 ≤ X ≤ 10^18^$
* Ghilimelele din output sunt pentru claritate. Ele nu trebuie afisate.
* IWD va sugereaza sa folositi tipul de date pe $64$ de biti, si anume $long long$.

* $0 ≤ X ≤ 10^18^$
* Ghilimelele din output sunt pentru claritate. Ele nu trebuie afişate.
* IWD va sugerează sa folosiţi tipul de date pe $64$ de biţi, şi anume $long long$.

h2. Exemplu