즐거운 삶을 위한 노력

더 나은 삶을 위해 사람들은 공공장소에 특별한 장치를 설치했다. 이 장치는 키보드와 화면으로 입출력을 주고받으며, 내부에 정수 하나를 저장한다. 처음 저장된 정수는 1이다.

장치는 다음 순서로 작동한다.

1. 사용자가 키보드로 정수 하나를 입력한다.
2. 장치는 현재 저장된 수에 입력된 수를 곱해 다시 저장한다.
3. 장치는 저장된 수가 완전제곱수인지 화면에 출력한다.

사람들이 입력하는 수가 순서대로 주어질 때, 각 사용 후 저장된 수가 완전제곱수인지 판별하라.

첫째 줄에 장치를 이용하는 사람의 수 N이 주어진다.

다음 N개의 줄에는 사람들이 입력한 정수 a_i가 이용 순서대로 한 줄에 하나씩 주어진다.

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

장치에 저장되는 수는 64비트 정수 범위를 벗어날 수 있다.

각 사용 후 장치에 저장된 수가 완전제곱수이면 DA를, 아니면 NE를 입력 순서대로 한 줄에 하나씩 출력한다.