Problema Piscina

Perfecționistul de Darius vrea să își amplaseze o piscină în curtea sa imensă ce are formă de dreptunghi. Compania care se ocupă de proiect îi oferă lui Darius o reducere semnificativă dacă forma pe care o are piscina este în formă de un poligon regulat (triunghi echilateral, pătrat, pentagon, hexagon, …). Darius este de acord cu această condiție, dar ar mai vrea, pe lângă aceasta, ca poligonul să poată să aibă cel puțin câte o latură paralelă cu fiecare latură a curții sale.

Cerință

Dându-se n numere naturale, să se determine pentru fiecare număr x dacă piscina poate fi reprezentată de un poligon regulat cu x laturi astfel încât să se satisfacă condiția lui Darius.

Formal, pentru fiecare număr x, să se verifice dacă în sistemul xOy, poligonul regulat cu x laturi poate sau nu să fie rotit astfel încât cel puțin o latură a poligonului să fie paralelă cu axa Ox și cel puțin o latură a poligonului să fie paralelă cu axa Oy.

Date de intrare

Programul citește de la tastatură, de pe prima linie, numărul natural n, iar de pe următoarele n linii, n numere naturale, semnificând valorile posibile date.

Date de ieșire

Programul afișează pe ecran pe n linii câte un mesaj: dacă a i-a valoare dintre cele n respectă criteriile, atunci pe a i-a linie se afișează mesajul DA, iar în caz contrar se afișează mesajul NU, unde 1 ≤ i ≤ n.

Restricții și precizări

• 1 ≤ n ≤ 10.000
• 3 ≤ cele n numere naturale ≤ 2.000.000.000

Exemplu