Na tabli je zapisan broj 1. Imamo niz od N prirodnih brojeva a i u i-tom koraku (1 ≤ i ≤ N) brišemo trenutni broj na tabli i umesto njega pišemo proizvod njega i broja
ai. Posle svakog koraka odrediti da li je trenutni broj na tabli potpun kvadrat.

U prvom redu standardnog ulaza nalazi se prirodan broj N koji predstavlja dužinu niza a. U svakom od narednih N redova nalazi se po jedan element niza a, u redosledu kojim množe trenutni broj na tabli.

Za svaki element niza a, u redosledu datim na ulazu, ispisati 'DA' ukoliko je njegov proizvod sa trenutnim brojem na tabli potpun kvadrat a inače ispisati 'NE' (velika slova, bez navodnika). Svaki odgovor ispisati u posebnom redu.

1 ≤ N ≤ 500.000

1 ≤ ai ≤ 1.000.000.

Na tabli će, redom, biti ispisani brojevi 1·2=2 (nije kvadrat), 1·2·3=6 (nije kvadrat), 1·2·3·6=36 (potpun kvadrat), 1·2·3·6·15=540 (nije kvadrat), 1·2·3·6·15·35=18900 (nije kvadrat), 1·2·3·6·15·35·21=396900 (potpun kvadrat), 1·2·3·6·15·35·21·64=25401600 (potpun kvadrat).

Obratiti pažnju da trenutni broj na tabli ne mora stati čak ni u 64-bitni tip podataka.