Efforts for a Joyful Life

To improve everyday life, people installed a special device in a public place. The device communicates through a keyboard and a screen, and it stores one integer internally. Initially, the stored integer is 1.

The device works in the following order.

1. A user enters one integer with the keyboard.
2. The device multiplies the currently stored number by the entered number and stores the result.
3. The device displays whether the stored number is a perfect square.

Given the numbers entered by the users in order, determine after each use whether the stored number is a perfect square.

The first line contains the number of users N.

Each of the next N lines contains one integer a_i, in the order the users enter them.

• 1 <= N <= 500,000
• 1 <= a_i <= 1,000,000

The number stored in the device may exceed the range of a 64-bit integer.

After each use, output DA if the number stored in the device is a perfect square, and NE otherwise. Print the answers in input order, one per line.