Yunzi vừa được học về số nguyên tố. Một số nguyên tố là số nguyên lớn hơn ~1~ và chỉ có đúng hai ước nguyên dương là ~1~ và chính nó.

Cho số nguyên ~n~, hãy giúp Yunzi in ra tất cả các số nguyên tố không vượt quá ~n~.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa một số nguyên ~n~.

Kết quả

In ra trên một dòng tất cả các số nguyên tố không vượt quá ~n~ theo thứ tự tăng dần, hai số liên tiếp cách nhau bởi một dấu cách.

Nếu không có số nguyên tố nào thoả mãn thì không in ra gì.

Ví dụ

Đầu vào:

15

Đầu ra:

2 3 5 7 11 13

Giải thích: Các số nguyên tố không vượt quá ~15~ là ~2, 3, 5, 7, 11, 13~. Số ~1~ không phải số nguyên tố vì chỉ có một ước dương, còn ~9 = 3 \times 3~ và ~15 = 3 \times 5~ đều có nhiều hơn hai ước.

Giới hạn

• ~1 \le n \le 2 \cdot 10^6~

Trong số học, phi hàm Euler ~\varphi(n)~ của một số nguyên dương ~n~ được định nghĩa là số lượng các số nguyên dương không vượt quá ~n~ và nguyên tố cùng nhau với ~n~ (nghĩa là có ước chung lớn nhất với ~n~ bằng ~1~).

Per phải tính ~\varphi(n)~ cho rất nhiều giá trị ~n~ khác nhau. Các bạn học viên hãy giúp Per nhé!

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~T~ — số lượng bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~.

Kết quả

In ra ~T~ dòng, dòng thứ ~i~ là giá trị ~\varphi(n)~ của bộ test thứ ~i~.

Ví dụ

Đầu vào:

5
1
2
3
4
5

Đầu ra:

1
1
2
2
4

Giải thích: Với ~n = 4~, các số không vượt quá ~4~ và nguyên tố cùng nhau với ~4~ là ~1~ và ~3~, nên ~\varphi(4) = 2~. Với ~n = 5~ thì cả ~1, 2, 3, 4~ đều nguyên tố cùng nhau với ~5~, nên ~\varphi(5) = 4~. Theo quy ước, ~\varphi(1) = 1~.

Giới hạn

• ~1 \le T \le 20000~
• ~1 \le n \le 10^6~

Khi học về số nguyên tố, Per đã nghĩ ra một loại số mới gọi là số Bar. Số nguyên tố có đúng ~2~ ước dương, còn số Bar thì có đúng ~3~ ước dương.

Cho một mảng ~a~ gồm ~n~ số nguyên. Với mỗi số, hãy xác định giúp Per xem nó có phải số Bar hay không.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — số lượng phần tử của mảng ~a~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.

Kết quả

Với mỗi số, in ra trên một dòng YES nếu số đó là số Bar, ngược lại in ra NO.

Ví dụ

Đầu vào:

3
2 9 3

Đầu ra:

NO
YES
NO

Giải thích: Số ~9~ có đúng ba ước là ~1, 3, 9~ nên là số Bar. Số ~2~ và số ~3~ đều là số nguyên tố, chỉ có hai ước nên không phải số Bar.

Giới hạn

• ~1 \le n \le 10^5~
• ~1 \le a_i \le 10^{12}~

Lại là một bài toán khác thầy giáo giao cho Per:

Cho ba số nguyên dương ~x~, ~y~, ~z~. Gọi ~XYZ(k)~ là số nguyên dương nhỏ nhất có đúng ~k~ chữ số và chia hết cho cả ~x~, ~y~ và ~z~. Trong trường hợp không tồn tại số như vậy thì ~XYZ(k) = -1~.

Số có đúng ~k~ chữ số là số nằm trong đoạn ~[10^{k-1}, 10^k - 1]~ (không có chữ số ~0~ ở đầu).

Với số ~n~ cho trước, hãy tính ~F(n) = \sum_{k=1}^{n} XYZ(k)~.

Vì đáp án có thể rất lớn nên hãy chia dư cho ~10^9 + 7~.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa bốn số nguyên ~x~, ~y~, ~z~ và ~n~.

Kết quả

In ra giá trị ~F(n)~ đã chia dư cho ~10^9 + 7~. Đáp án phải là một số trong đoạn ~[0, 10^9 + 6]~.

Ví dụ

Đầu vào:

2 3 5 4

Đầu ra:

1169

Giải thích: Bội chung nhỏ nhất của ~2~, ~3~, ~5~ là ~30~. Không có số một chữ số nào chia hết cho ~30~ nên ~XYZ(1) = -1~. Tiếp theo ~XYZ(2) = 30~, ~XYZ(3) = 120~, ~XYZ(4) = 1020~. Vậy ~F(4) = -1 + 30 + 120 + 1020 = 1169~.

Giới hạn

• ~1 \le x, y, z \le 10^4~
• ~1 \le n \le 16~

Per được cho một mảng ~a~ gồm ~n~ số nguyên dương. Nhiệm vụ của Per là tìm ra cặp hai phần tử có ước chung lớn nhất (GCD) lớn nhất có thể.

Nói cách khác, hãy tìm giá trị lớn nhất của ~\gcd(a_i, a_j)~ trên mọi cặp chỉ số ~1 \le i < j \le n~.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~n~ — số lượng phần tử của mảng ~a~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.

Kết quả

In ra giá trị ~\gcd~ lớn nhất tìm được.

Ví dụ

Đầu vào:

4
2 10 6 9

Đầu ra:

3

Giải thích: Cặp ~(6, 9)~ có ~\gcd(6, 9) = 3~. Các cặp còn lại cho giá trị nhỏ hơn: ~\gcd(2, 10) = 2~, ~\gcd(2, 6) = 2~, ~\gcd(10, 6) = 2~, ~\gcd(2, 9) = \gcd(10, 9) = 1~.

Giới hạn

• ~2 \le n \le 2 \cdot 10^5~
• ~1 \le a_i \le 10^6~

Sau khi thành thạo sàng Eratosthenes, Yunzi gặp một bài toán khó hơn: các số cần xét quá lớn để sàng từ ~1~.

Cho hai số nguyên ~L~ và ~R~, hãy in ra tất cả các số nguyên tố nằm trong đoạn ~[L, R]~.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa hai số nguyên ~L~ và ~R~.

Kết quả

In ra trên một dòng tất cả các số nguyên tố thuộc đoạn ~[L, R]~ theo thứ tự tăng dần, hai số liên tiếp cách nhau bởi một dấu cách.

Nếu trong đoạn không có số nguyên tố nào thì không in ra gì.

Ví dụ

Đầu vào:

20 30

Đầu ra:

23 29

Giải thích: Trong đoạn ~[20, 30]~ chỉ có ~23~ và ~29~ là số nguyên tố.

Giới hạn

• ~1 \le L \le R \le 10^{12}~
• ~1 \le R - L + 1 \le 10^6~

Sau khi học được phép lũy thừa nhị phân, Per được thầy giáo cho bài toán sau:

Cho ba số nguyên không âm ~a~, ~b~, ~c~, hãy tính nhanh giá trị ~a^{b^c}~ chia dư cho ~10^9 + 7~.

Lưu ý rằng ~a^0 = 1~ với mọi ~a~ (kể cả ~a = 0~).

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~q~ — số lượng truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a~, ~b~, ~c~.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là giá trị ~a^{b^c}~ chia dư cho ~10^9 + 7~ của truy vấn thứ ~i~.

Ví dụ

Đầu vào:

1
2 3 1

Đầu ra:

8

Giải thích: ~b^c = 3^1 = 3~, nên đáp án là ~2^3 = 8~.

Giới hạn

• ~1 \le q \le 10^5~
• ~0 \le a, b, c \le 10^9~

Cho một số nguyên dương ~m~, nhiệm vụ của bạn là tìm số lượng ước, tổng các ước và tích các ước của nó.

Vì ~m~ có thể rất lớn nên nó được cho dưới dạng phân tích thừa số nguyên tố:

~m = p_1^{x_1} \cdot p_2^{x_2} \cdot \ldots \cdot p_n^{x_n}~

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên dương ~n~.
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~p~ và ~x~ — một số nguyên tố và số mũ của nó. Các số nguyên tố ~p~ đôi một khác nhau.

Kết quả

In ra ba số nguyên đã chia dư cho ~10^9 + 7~: số lượng ước, tổng các ước và tích các ước của ~m~.

Ví dụ

Đầu vào:

2
2 1
3 2

Đầu ra:

6 39 5832

Giải thích: Test mẫu chính là phân tích của ~m = 2^1 \cdot 3^2 = 18~.

• Các ước của ~18~ là ~1, 2, 3, 6, 9, 18~ — có ~6~ ước.
• Tổng các ước là ~1 + 2 + 3 + 6 + 9 + 18 = 39~.
• Tích các ước là ~1 \cdot 2 \cdot 3 \cdot 6 \cdot 9 \cdot 18 = 5832~.

Giới hạn

• ~1 \le n \le 10^5~
• ~2 \le p \le 10^6~, các ~p~ đôi một khác nhau
• ~1 \le x \le 10^9~

Gọi ~f(i, j)~ là tổng của tất cả các ước nguyên dương chung của ~i~ và ~j~. Ví dụ ~f(8, 12) = 1 + 2 + 4 = 7~.

Cho số nguyên dương ~n~, hãy tính

~S = \sum_{i=1}^{n} \sum_{j=i}^{n} f(i, j)~

Vì đáp án có thể rất lớn nên hãy chia dư cho ~10^9 + 7~.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa một số nguyên ~n~.

Kết quả

In ra giá trị ~S~ đã chia dư cho ~10^9 + 7~.

Ví dụ

Đầu vào:

5

Đầu ra:

33

Giải thích: Với ~n = 5~, tổng được lấy trên ~15~ cặp ~(i, j)~ với ~i \le j~. Chẳng hạn ~f(1, 1) = 1~, ~f(2, 4) = 1 + 2 = 3~, ~f(4, 4) = 1 + 2 + 4 = 7~. Cộng tất cả lại được ~33~.

Giới hạn

• ~1 \le n \le 10^{14}~

Bạn được cho một số nguyên tố ~p~, ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ và một số nguyên ~k~.

Hãy tìm số cặp chỉ số ~(i, j)~ với ~1 \le i < j \le n~ sao cho

~(a_i + a_j)(a_i^2 + a_j^2) \equiv k \pmod p~

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~n~, ~p~ và ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~. Tất cả các phần tử đều khác nhau.

Kết quả

In ra số cặp thoả mãn.

Ví dụ

Đầu vào:

3 3 0
0 1 2

Đầu ra:

1

Đầu vào:

6 7 2
1 2 3 4 5 6

Đầu ra:

3

Giải thích: Ở ví dụ đầu tiên, ~(0 + 1)(0^2 + 1^2) = 1 \equiv 1~, ~(0 + 2)(0^2 + 2^2) = 8 \equiv 2~, còn ~(1 + 2)(1^2 + 2^2) = 15 \equiv 0 \pmod 3~. Vậy chỉ có một cặp thoả mãn.

Ở ví dụ thứ hai có ~3~ cặp là ~(1, 5)~, ~(2, 3)~ và ~(4, 6)~.

Giới hạn

• ~2 \le n \le 3 \cdot 10^5~
• ~2 \le p \le 10^9~, ~p~ là số nguyên tố
• ~0 \le k \le p - 1~
• ~0 \le a_i \le p - 1~, các ~a_i~ đôi một khác nhau

Sau khi thành thạo sàng Eratosthenes, Yunzi tự tin rằng không số nguyên tố nào làm khó được mình. Thầy giáo mỉm cười và đưa ra một danh sách các con số khổng lồ — lớn đến mức không thể sàng, cũng không thể chia thử từng ước.

Cho ~T~ số nguyên, với mỗi số hãy cho biết nó có phải số nguyên tố hay không.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~T~ — số lượng truy vấn.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~a~.

Kết quả

Với mỗi số, in ra trên một dòng YES nếu số đó là số nguyên tố, ngược lại in ra NO.

Ví dụ

Đầu vào:

5
1
2
561
999999999999999989
1000000000000000000

Đầu ra:

NO
YES
NO
YES
NO

Giải thích: Số ~1~ không phải số nguyên tố. Số ~2~ là số nguyên tố chẵn duy nhất. Số ~561 = 3 \times 11 \times 17~ là hợp số — đây là số Carmichael nhỏ nhất, nổi tiếng vì đánh lừa phép thử Fermat với hầu hết cơ số. Số ~999999999999999989~ là số nguyên tố lớn nhất không vượt quá ~10^{18}~.

Giới hạn

• ~1 \le T \le 10^5~
• ~1 \le a \le 10^{18}~

Chia thử đến ~\sqrt{a}~ tốn ~10^9~ phép chia cho một số nguyên tố cỡ ~10^{18}~, chắc chắn quá thời gian. Hãy dùng thuật toán Miller-Rabin: viết ~a - 1 = 2^k \cdot m~ với ~m~ lẻ, rồi kiểm tra điều kiện ~x^m \equiv 1~ hoặc ~x^{2^l m} \equiv -1 \pmod a~ với từng cơ số ~x~. Với bộ cơ số ~\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}~, kết quả đã được chứng minh là chính xác tuyệt đối cho mọi ~a < 2^{64}~.

Chú ý bẫy tràn số: ~a~ lên đến ~10^{18}~ nên tích hai số dư trong quá trình lũy thừa vượt quá long long — hãy dùng __int128 cho phép nhân trung gian.