시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 64 19 17 42.500%

문제

더 나은 삶을 위해 사람들은 특이한 장치 하나를 공공장소에 놓기로 결정했다. 이 장치는 키보드와 화면을 통해 입출력을 주고받으며, 내부에 정수 하나를 저장한다. 초기에 저장되어있는 정수는 1이다.

이 장치는 아래와 같은 과정으로 작동한다.

  • 사용자는 키보드를 통해 정수 하나를 입력한다.
  • 이 장치는 원래의 수에 입력된 수를 곱해 저장한다.
  • 그러고 나면 결과가 완전제곱수인지를 화면에 출력한다. 만약 완전제곱수가 맞을 경우 사용자는 기쁘게 춤을 추고 뛰며 다른 사람들에게 걸리지 않도록 조심스럽게 장치로부터 다른 곳으로 간다.

사람들이 입력하는 수가 순서대로 주어졌을 때, 누가 기쁘게 되는지를 알아내시오.

입력

첫 번째 줄에는 이 장치를 이용하는 사람의 수 N(1 ≤ N ≤ 500 000)이 들어온다.

다음 N개의 줄에는 사람들이 입력한 정수 ai(1 ≤ ai ≤ 1 000 000)가 사용하는 순서대로 한 줄에 하나씩 들어온다.

장치에 저장되는 수의 범위가 64비트 int형의 범위를 벗어날 수도 있음에 유의하라.

출력

장치에 저장된 수가 완전제곱수이면 "DA"를, 그렇지 않다면 "NE"를 각각의 사용자가 얻는 순서대로 출력하시오.

예제 입력 1

7
2
3
6
15
35
21
64

예제 출력 1

NE
NE
DA
NE
NE
DA
DA
W3sicHJvYmxlbV9pZCI6IjMxNDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5OTBcdWFjNzBcdWM2YjQgXHVjMGI2XHVjNzQ0IFx1YzcwNFx1ZDU1YyBcdWIxNzhcdWI4MjUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjM1NCBcdWIwOThcdWM3NDAgXHVjMGI2XHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDAgXHVkMmI5XHVjNzc0XHVkNTVjIFx1YzdhNVx1Y2U1OCBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2Y1XHVhY2Y1XHVjN2E1XHVjMThjXHVjNWQwIFx1YjE5M1x1YWUzMFx1Yjg1YyBcdWFjYjBcdWM4MTVcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWM3YTVcdWNlNThcdWIyOTQgXHVkMGE0XHViY2Y0XHViNGRjXHVjNjQwIFx1ZDY1NFx1YmE3NFx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHVjNzg1XHVjZDljXHViODI1XHVjNzQ0IFx1YzhmY1x1YWNlMFx1YmMxYlx1YzczY1x1YmE3MCwgXHViMGI0XHViZDgwXHVjNWQwIFx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTVjXHViMmU0LiBcdWNkMDhcdWFlMzBcdWM1ZDAgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1YjI5NCAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjN2E1XHVjZTU4XHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzNjXHViODVjIFx1Yzc5MVx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWMwYWNcdWM2YTlcdWM3OTBcdWIyOTQgXHVkMGE0XHViY2Y0XHViNGRjXHViOTdjIFx1ZDFiNVx1ZDU3NCBcdWM4MTVcdWMyMTggXHVkNTU4XHViMDk4XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc0IFx1YzdhNVx1Y2U1OFx1YjI5NCBcdWM2ZDBcdWI3OThcdWM3NTggXHVjMjE4XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YjQxYyBcdWMyMThcdWI5N2MgXHVhY2YxXHVkNTc0IFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZGY4XHViN2VjXHVhY2UwIFx1YjA5OFx1YmE3NCBcdWFjYjBcdWFjZmNcdWFjMDAgXHVjNjQ0XHVjODA0XHVjODFjXHVhY2YxXHVjMjE4XHVjNzc4XHVjOWMwXHViOTdjIFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM2NDRcdWM4MDRcdWM4MWNcdWFjZjFcdWMyMThcdWFjMDAgXHViOWRlXHVjNzQ0IFx1YWNiZFx1YzZiMCBcdWMwYWNcdWM2YTlcdWM3OTBcdWIyOTQgXHVhZTMwXHVjMDU4XHVhYzhjIFx1Y2RhNFx1Yzc0NCBcdWNkOTRcdWFjZTAgXHViNmYwXHViYTcwIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVhYzc4XHViOWFjXHVjOWMwIFx1YzU0YVx1YjNjNFx1Yjg1ZCBcdWM4NzBcdWMyZWNcdWMyYTRcdWI3ZmRcdWFjOGMgXHVjN2E1XHVjZTU4XHViODVjXHViZDgwXHVkMTMwIFx1YjJlNFx1Yjk3OCBcdWFjZjNcdWM3M2NcdWI4NWMgXHVhYzA0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIyMDRcdWFjMDAgXHVhZTMwXHVjMDU4XHVhYzhjIFx1YjQxOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3NzQgXHVjN2E1XHVjZTU4XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyA1MDAgMDAwKVx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjNzg1XHViODI1XHVkNTVjIFx1YzgxNVx1YzIxOCBhPHN1Yj5pPFwvc3ViPigxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDApXHVhYzAwIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3YTVcdWNlNThcdWM1ZDAgXHVjODAwXHVjN2E1XHViNDE4XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWJjOTRcdWM3MDRcdWFjMDAgNjRcdWJlNDRcdWQyYjggaW50XHVkNjE1XHVjNzU4IFx1YmM5NFx1YzcwNFx1Yjk3YyBcdWJjOTdcdWM1YjRcdWIwYTAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1Yzc0Y1x1YzVkMCBcdWM3MjBcdWM3NThcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjN2E1XHVjZTU4XHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWMyMThcdWFjMDAgXHVjNjQ0XHVjODA0XHVjODFjXHVhY2YxXHVjMjE4XHVjNzc0XHViYTc0ICZxdW90O0RBJnF1b3Q7XHViOTdjLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0ICZxdW90O05FJnF1b3Q7XHViOTdjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMwYWNcdWM2YTlcdWM3OTBcdWFjMDAgXHVjNWJiXHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBPVFBVTkkiLCJkZXNjcmlwdGlvbiI6IjxwPlRvIG1ha2UgZXZlcnlkYXkgbGlmZSBiZXR0ZXIsIGl0IGhhcyBiZWVuIGRlY2lkZWQgdGhhdCBhIG1vc3QgdW51c3VhbCBkZXZpY2UgYmUgcGxhY2VkIGluIGEgcHVibGljIGxvY2F0aW9uLiBUaGUgZGV2aWNlIGludGVyYWN0cyB3aXRoIHVzZXJzIHdpdGggYSBrZXlib2FyZCBhbmQgYSBzY3JlZW4sIGFuZCBzdG9yZXMgYW4gaW50ZWdlciBpbnRlcm5hbGx5LCB3aGljaCBpcyBpbml0aWFsbHkgMS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGRldmljZSBpcyB1c2VkIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIHVzZXIgZW50ZXJzIGFuIGludGVnZXIgdXNpbmcgdGhlIGtleWJvYXJkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5UaGUgZGV2aWNlIG11bHRpcGxpZXMgdGhlIGludGVybmFsIG51bWJlciB3aXRoIHRoZSBlbnRlcmVkIG51bWJlciBhbmQgc3RvcmVzIHRoZSByZXN1bHQuPFwvbGk+XHJcblx0PGxpPlRoZSBkZXZpY2Ugb3V0cHV0cyB3aGV0aGVyIHRoZSByZXN1bHQgaXMgYSBwZXJmZWN0IHNxdWFyZSAoYSBwZXJmZWN0IHNxdWFyZSBpcyBhbiBpbnRlZ2VyIHdoaWNoIGlzIHRoZSBzcXVhcmUgb2Ygc29tZSBpbnRlZ2VyKSBvbiB0aGUgc2NyZWVuLiBJZiBpdCBpcywgdGhlIHVzZXIgY2hlZXJzLCBqdW1wcywga2lja3MgaGlzIGhlZWxzIGluIHRoZSBhaXIgYmVmb3JlIGxhbmRpbmcgYW5kLCBoYXBweSBvbiB0aGUgaW5zaWRlIGJ1dCBjYXJlZnVsIG5vdCB0byBzaG93IG9mZiwgZGlzY3JldGVseSBtb3ZlcyBhd2F5IGZyb20gdGhlIGRldmljZS4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIG51bWJlcnMgdXNlcnMgZW50ZXIgaW4gb3JkZXIsIGRldGVybWluZSB3aGljaCB1c2VycyB0aGUgZGV2aWNlIG1ha2VzIGhhcHB5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDUwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHVzZXJzIG9mIHRoZSBkZXZpY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIGludGVnZXJzIGVudGVyZWQgYnkgdGhlIHVzZXJzLCBpbiBvcmRlciBpbiB3aGljaCB0aGV5IHVzZSB0aGUgZGV2aWNlLCBvbmUgcGVyIGxpbmUuIFRoZSBpbnRlZ2VycyB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMSAwMDAgMDAwIChhIG1pbGxpb24pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlIHRoYXQgdGhlIHN0b3JlZCBpbnRlZ2VyIG1heSBub3QgZml0IGluIGEgNjQtYml0IGludGVnZXIgdHlwZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGFuc3dlciBlYWNoIG9mIHRoZSB1c2VycyBnZXRzLCBpbiBvcmRlciBpbiB3aGljaCB0aGV5IHVzZSB0aGUgZGV2aWNlLiBUaGUgZGV2aWNlIG91dHB1dHMgJnF1b3Q7REEmcXVvdDsgaWYgdGhlIHN0b3JlZCBpbnRlZ2VyIGlzIGEgY29tcGxldGUgc3F1YXJlLCBhbmQgJnF1b3Q7TkUmcXVvdDsgaWYgaXQgaXMgbm90LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==