ĐỨA TRẺ MAY MẮN

Trong công viên, người ta đặt một chiếc máy tặng quà cho trẻ em đến chơi. Người chơi sẽ tương tác với máy thông qua một màn hình và bàn phím.

Vào mỗi buổi sáng, chiếc máy đó tự động khởi tạo giá trị hiện trên màn hình bằng 1. Một đứa trẻ đến chơi sẽ bấm một số nguyên dương trên bàn phím, máy sẽ nhân số trên màn hình với số đã được đứa trẻ bấm và hiện kết quả trên màn hình (đồng thời lưu lại số đó), nếu kết quả đó là số chính phương máy sẽ tự động nhả ra một món quà cho trẻ.

Hôm nay, có  đứa trẻ đã đến chơi (đánh số thứ tự từ 1 đến ), mỗi đứa trẻ sẽ bấm một số trên bàn phím. Hãy xác định những đứa trẻ nhận được quà.

Dữ liệu vào:

• Dòng đầu tiên là số  – số đứa trẻ dùng máy tặng quà;
•  dòng tiếp theo, mỗi dòng là một số nguyên dương (thuộc đoạn [1, 1.000.000]) – là số nguyên mà đứa trẻ nhập vào máy.

Kết quả ra:

• Gồm  dòng, mỗi dòng chứa kết quả là “DA” nếu đứa trẻ tương ứng là đứa trẻ may mắn, ngược lại thì đưa ra kết quả là “NE”.

Ví dụ:

Ràng buộc:

• Subtask 1: 40% số test đầu tiên
• Subtask 2: 60% số test cuối cùng không có ràng buộc gì thêm