Lý thuyết số

Số hoàn hảo là số có tổng các ước thực sự (các ước nhỏ hơn chính nó) bằng chính nó. Nhập vào số nguyên \(n\) và kiểm tra xem \(n\) có phải là số hoàn hảo hay không.

Input

• Một dòng duy nhất chứa số nguyên dương \(n\) (\(1 \le n \le 10^7\)).

Output

• In ra YES nếu \(n\) là số hoàn hảo, ngược lại in ra NO.

Example

6

YES

10

NO

Số tương lai là số có tổng các ước là một số nguyên tố. Ví dụ: số 4 có các ước \(1, 2, 4\) có tổng bằng \(7\) là một số nguyên tố nên \(4\) là số tương lai. Viết chương trình nhập vào số nguyên \(t\) (\(t \le 10\)) và \(t\) số nguyên \(n\). Với mỗi số nguyên \(n\) kiểm tra xem \(n\) có phải số tương lai không.

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(t \le 10\)).
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\) (\(n \le 10^6\)).

Output

• Với mỗi số \(n\), in ra YES nếu đó là số tương lai, ngược lại in ra NO.

Example

2
4
6

YES
NO

Số nguyên tố toàn diện là một số nguyên tố và tổng các chữ số của nó cũng là số nguyên tố. Ví dụ: \(2, 3, 5, 7, 11, 23\) là các số nguyên tố toàn diện còn \(13\) thì không (vì \(1 + 3 = 4\) không phải là số nguyên tố).

Yêu cầu: Viết chương trình nhập vào số nguyên \(t\) (\(t \le 100\)) và \(t\) số nguyên \(n\), sau đó kiểm tra xem mỗi số \(n\) có phải là số nguyên tố toàn diện hay không.

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \le t \le 100\)) là số lượng test case.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\) (\(1 \le n \le 10^9\)).

Output

• Với mỗi số nguyên \(n\), in ra YES nếu \(n\) là số nguyên tố toàn diện, ngược lại in ra NO.

Example

3
23
13
11

YES
NO
YES

Số siêu nguyên tố là một số nguyên tố mà khi ta lần lượt xóa đi từng chữ số tận cùng bên phải, các số còn lại vẫn luôn là số nguyên tố.

Ví dụ: \(239\) là số nguyên tố, xóa đi chữ số \(9\) ta được \(23\) là số nguyên tố, xóa tiếp chữ số \(3\) ta được \(2\) cũng là số nguyên tố. Vậy \(239\) là số siêu nguyên tố.

Viết chương trình kiểm tra xem một số nguyên \(n\) cho trước có phải là số siêu nguyên tố hay không.

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \le t \le 20\)) là số lượng test case.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\) (\(0 \le n \le 10^9\)).

Output

• Đối với mỗi test case, in ra YES nếu \(n\) là số siêu nguyên tố, ngược lại in ra NO trên một dòng.

Example

2
239
13

YES
NO

Một số nguyên \(n\) được gọi là số nguyên tố mở rộng nếu bản thân \(n\) là một số nguyên tố, và khi ta viết thêm đúng một chữ số bất kỳ (từ \(0\) đến \(9\)) vào tận cùng bên phải của \(n\), ta có thể tạo ra ít nhất một số nguyên tố mới.

Ví dụ:

• \(23\) là số nguyên tố. Khi thử ghép thêm các chữ số từ \(0\) đến \(9\) vào bên phải, ta được hai số nguyên tố mới là \(233\) và \(239\). Vậy \(23\) là số nguyên tố mở rộng.
• \(33\) không phải là số nguyên tố, nên không được xét.

Viết chương trình kiểm tra một số nguyên \(n\) cho trước và liệt kê tất cả các số nguyên tố mới có thể tạo thành từ nó.

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \le t \le 100\)) là số lượng test case.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\) (\(0 \le n \le 10^9\)).

Output

• Đối với mỗi test case, nếu \(n\) là số nguyên tố mở rộng, hãy in ra tất cả các số nguyên tố mới tạo thành theo thứ tự tăng dần, cách nhau bởi một khoảng trắng.
• Nếu \(n\) không phải là số nguyên tố, hoặc không thể tạo ra bất kỳ số nguyên tố mới nào, in ra -1.

Example

3
23
13
33

233 239
131 137 139
-1

Số bán nguyên tố là số có dạng \(n = p \cdot q\) với \(p\), \(q\) là các số nguyên tố và có thể bằng nhau. Ví dụ \(6\) là bán nguyên tố vì \(6 = 2 \cdot 3\) hoặc \(4 = 2 \cdot 2\). Nhập vào số nguyên dương \(n\) và kiểm tra xem \(n\) có phải là số bán nguyên tố hay không.

Input

• Số nguyên dương \(n\) (\(1 \le n \le 10^6\)).

Output

• In ra YES nếu \(n\) là số bán nguyên tố ngược lại in NO.

Example

6

YES

5

NO

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 1000\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^6\).

Cho một số nguyên dương \(n\). Hãy kiểm tra xem \(n\) có phải là số tìm ẩn hay không.

(Lưu ý: Số tìm ẩn là số nguyên dương chia hết cho tổng các ước nguyên tố phân biệt của chính nó. Ước nguyên tố là các số vừa là ước của \(n\) vừa là số nguyên tố).

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \le t \le 100\)) là số lượng test case.
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\) (\(1 \le n \le 10^9\)).

Output

• Đối với mỗi test case, in ra YES nếu \(n\) là số tìm ẩn, ngược lại in ra NO trên một dòng.

Example

2
30
12

YES
NO

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(n \le 10^9\)