Chúng ta đã quá rõ việc một số nguyên tố (prime) là số nguyên dương lớn hơn ~1~ có duy nhất hai ước là ~1~ và chính nó. Để làm mới bài toán, hôm nay, ta sẽ định nghĩa một số TPrime là một số nguyên dương lớn hơn ~1~ gồm đúng ~3~ ước.

Cho ~n~ truy vấn, mỗi truy vấn là một số ~a~, hãy kiểm tra xem số này có phải là số TPrime hay không.

Input

• Dòng ~1~ ghi số nguyên dương ~n~ ~(1 \le n \le 3*10^5)~
• ~n~ dòng sau, mỗi dòng gồm một số nguyên dương ~a~ ~(1 \le a \le 10^{12})~ miêu tả truy vấn.

Output

• In ra ~n~ dòng, với mỗi truy vấn, nếu ~a~ là số TPrime thì in ra "YES", ngược lại in ra "NO".

Subtask

• Có ~20\%~ số test ứng với ~1 \le n \le 100, 1 \le a \le 10^4~
• Có ~30\%~ số test ứng với ~1 \le n,a \le 10^5~
• Có ~50\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

3
4
6
7

Sample Output 1

YES
NO
NO

Cho 2 dãy số nguyên dương ~a~ có ~n~ phần tử và ~b~ có ~m~ phần tử. Với ~j~ từ 1 đến ~m~ hãy tìm ~gcd(a_1 + b_j, a_2 + b_j,...,a_n + b_j)~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~1 \le n, m \le 2 \times 10^5~.
• Dòng thứ 2 gồm ~n~ số nguyên dương ~1 \le a_i \le 10^9~.
• Dong thứ 3 gồm ~n~ số nguyên dương ~1 \le b_j \le 10^9~.

Output

• In ra ~m~ số nguyên tương ứng với đáp án.

Sample Test

Input:

4 4
1 25 121 169
1 2 7 23

Output:

2 3 8 24

Cho ~3~ số nguyên tố ~a~, ~b~, ~c~ và số nguyên dương ~n~, hãy đếm xem trong khoảng từ ~1~ tới ~n~, có bao nhiêu số chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Input

• Gồm một dòng chứa ~4~ số ~a,b,c,n~, trong đó ~a,b,c~ là số nguyên tố và đôi một khác nhau, ~n~ là một số nguyên dương.

Output

• In ra số số nguyên dương trong khoảng ~[1,n]~ chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Điều kiện

• ~1 \le a,b,c \le 10^6~.
• ~1 \le n \le 10^{18}~.

Subtask

• ~50\%~ số điểm: ~n \le 10^6~.
• ~50\%~ số điểm: Không ràng buộc gì thêm.

Ví dụ

Input 1:

2 3 5 9

Output 1:

7

Input 2:

3 5 7 20

Output 2:

11

Cho số ~n~. Hãy tìm số ~k \le n~ lớn nhất sao cho ~k~ là tích của 3 số nguyên tố liên tiếp.

Input

• Gồm số tự nhiên ~n \le 10^{18}~.

Output

• Gồm duy nhất một số tự nhiên ~k~. Nếu không có số thỏa mãn in ra -1.

Sample Test

Input:

31

Output

30

Cho ~t~ truy vấn, mỗi truy vấn là một số nguyên dương ~n~, hãy in ra tổng các ước của số ~n~.

Input

• Dòng đầu tiên gồm một số nguyên dương miêu tả số ~t~ ~(1 \le t \le 3\times10^5)~

• ~t~ dòng sau, mỗi dòng gồm một số nguyên dương ~n~ ~(1 \le n \le 10^7)~ miêu tả truy vấn tương ứng.

  Output

• Với mỗi truy vấn, in ra kết quả tương ứng theo từng dòng.

Sample Test

Input:

4
10
8
15
16

Output:

18
15
24
31