POTPUNI

문제

To make everyday life better, it has been decided that a most unusual device be placed in a public location. The device interacts with users with a keyboard and a screen, and stores an integer internally, which is initially 1. 

The device is used as follows: 

• The user enters an integer using the keyboard. 
• The device multiplies the internal number with the entered number and stores the result.
• The device outputs whether the result is a perfect square (a perfect square is an integer which is the square of some integer) on the screen. If it is, the user cheers, jumps, kicks his heels in the air before landing and, happy on the inside but careful not to show off, discretely moves away from the device. 

Write a program that, given the numbers users enter in order, determine which users the device makes happy.

입력

The first line of input contains an integer N (1 ≤ N ≤ 500 000), the number of users of the device. 

The following N lines contain integers entered by the users, in order in which they use the device, one per line. The integers will be between 1 and 1 000 000 (a million). 

Note that the stored integer may not fit in a 64-bit integer type. 

출력

Output the answer each of the users gets, in order in which they use the device. The device outputs "DA" if the stored integer is a complete square, and "NE" if it is not. 

5
2
2
2
2
2

NE
DA
NE
DA
NE

7
2
3
6
15
35
21
64

NE
NE
DA
NE
NE
DA
DA

7
999999
111111
333333
111111
3
27
243

NE
DA
NE
NE
DA
NE
DA