Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Chỉ còn bức tranh cuối cùng thôi, đó là "Mai". Cương đã tìm được chỗ bán bức tranh Mai đẹp nhất thế giới. Bức tranh đó có ~n~ bông hoa mai.

Cơ mà tiền nào của nấy, vì đẹp nên bức tranh lại quá đắt, trong khi ngân quỹ còn có thể sử dụng là không nhiều. Cương quyết định mặc cả người bán hàng.

Người bán hàng đồng ý giảm giá bán của bức tranh xuống với một điều kiện, mỗi khi người bán hàng chỉ vào một bông hoa bất kì, Cương trả lời xem tích số cánh hoa của các bông hoa đã chỉ có phải số chính phương hay không.

Đơn thuần chỉ là tính toán thì không có gì, nhưng số lượng cánh hoa là khá lớn khiến máy tính cầm tay của Cương không thể tính nổi. Bạn hãy giúp Cương nhé.

Dữ liệu vào

• Dòng đầu tiên 1 số nguyên dương ~n~ ~(n \le 500000)~ — số lượng bông hoa mai.
• ~N~ dòng tiếp theo, mỗi dòng một số nguyên dương ~a~ ~(a \le 10^6)~ – số cánh hoa của bông hoa được chỉ ở lượt tương ứng.

Kết quả

• ~N~ dòng – tương ứng với ~N~ lần trả lời. YES nếu tích số cánh hoa của các bông hoa đã chỉ là số chính phương. NO nếu ngược lại.

Subtask

• Tích số cánh hoa của các bông hoa không vượt quá ~10^{18}~: ~30\%~.
• Mỗi bông hoa có số lượng cánh không quá ~500~: ~40\%~.
• Không giới hạn gì thêm: ~30\%~.

Sample Input 1

7
2
3
6
15
35
21
64

Sample Output 1

NO
NO
YES
NO
NO
YES
YES

Nguồn: HAUI OJ – HIT Open Day 2023.