#1634. BÓ HOA MAY MẮN (LUCKYBOU)

Bộ nhớ: 512 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Mùa xuân về trên vùng cao Sơn La, hoa Ban nở trắng xóa khắp các sườn núi. Để chuẩn bị cho Lễ hội Hoa Ban, các bạn học sinh trường Phổ thông Dân tộc Nội trú tỉnh được giao nhiệm vụ chuẩn bị các bó hoa trang trí.

Trong quan niệm của người dân nơi đây, một bó hoa gồm A_i bông hoa được coi là "Bó hoa May mắn" nếu số lượng bông hoa A_i của nó có đúng 3 ước số dương phân biệt (tượng trưng cho sự hòa hợp giữa Thiên - Địa - Nhân).

Nhiệm vụ của bạn là kiểm tra xem trong danh sách n bó hoa đã chuẩn bị, bó hoa nào là "Bó hoa May mắn".

Dữ liệu:

  • Dòng đầu tiên chứa một số nguyên dương n ( 1 \le n \le 10^5 ).
  • Dòng thứ hai chứa n số nguyên dương A_1, A_2, \dots, A_n là số lượng bông hoa trong mỗi bó ( 1 \le A_i \le 10^{12} ).

Kết quả:

  • Ghi trên n dòng, mỗi dòng ghi "YES" nếu bó hoa tương ứng là "Bó hoa May mắn", ngược lại ghi "NO".

Ví dụ:

Dữ liệu:

3
4 5 6

Kết quả:

YES
NO
NO

Dữ liệu:

2
1 9

Kết quả:

NO
YES

Giải thích:

  • Ở ví dụ 1:
    • Bó hoa có 4 bông có các ước là \{1, 2, 4\} (đúng 3 ước) \rightarrow YES.
    • Bó hoa có 5 bông có các ước là \{1, 5\} (2 ước) \rightarrow NO.
    • Bó hoa có 6 bông có các ước là \{1, 2, 3, 6\} (4 ước) \rightarrow NO.
  • Ở ví dụ 2:
    • Bó hoa có 1 bông chỉ có 1 ước là \{1\} \rightarrow NO.
    • Bó hoa có 9 bông có các ước là \{1, 3, 9\} (đúng 3 ước) \rightarrow YES.

Giới hạn:

  • Subtask #1 (20% số điểm): n \le 100, A_i \le 1000 .
  • Subtask #2 (30% số điểm): n \le 10^5, A_i \le 10^6 .
  • Subtask #3 (50% số điểm): n \le 10^5, A_i \le 10^{12} .