Tính tổng dãy số: ~1 - 3 + 5 - 7 + 9 - ..... + N~.

Input

• Dòng đầu tiên và duy nhất chứa 1 số tự nhiên lẻ N ~(N \le 10^9)~

Output

• In ra một số nguyên là đáp số của tổng trên.

Example

Input

9

Output

5

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Nam đố Quân bài toán sau: Cho dãy số gồm ~N~ số nguyên dương, các số trong dãy được đánh số bắt đầu từ 1. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số đó có bao nhiêu số nguyên tố. Ví dụ: Cho N=7, x=3, y =6, dãy số 3, 6, 2, 17, 11, 22, 19. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 6 có tất cả 3 số nguyên tố là: 2, 17, 11.

Yêu cầu: Cho dãy gồm có ~N~ số nguyên, ứng với mỗi cặp số ~x~, ~y~ hãy in ra số lượng các số nguyên tố từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~0≤N,q≤10^5~).
• Dòng 2: ghi giá trị dãy số ~a_1,a_2,…a_N~ (~1≤a_i≤10^7~) các số cách nhau một dấu cách.
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên.

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là số lượng các số nguyên tố từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

7 3
1 3 5 6 8 9 11
1 3
2 6
3 7

Output

2
2
2

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Cho số nguyên dương ~N~. Tính tổng trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số liên tiếp từ 1 đến N. Ví dụ: Cho N=7, x=3, y =6, dãy số từ 1 đến 10. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 6 có tất cả 2 số nguyên tố là: 3 và 5, nên tổng các số nguyên tố trong đoạn từ 3 đến 6 là 8.

Yêu cầu: Cho số nguyên dương ~N~, ứng với mỗi cặp số ~x~, ~y~ hãy tính tổng các số nguyên tố từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~0≤N,q≤10^6~).
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên (~0 ≤ x, y \le N~).

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là tổng các số nguyên tố từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

10 3
1 3
3 6
3 7

Output

5
8
15

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Cho dãy số gồm ~N~ số nguyên dương, các số trong dãy được đánh số bắt đầu từ 1. Tính tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số đó. Ví dụ: Cho N=7, x=3, y =6, dãy số 3, 6, 2, 17, 11, 22, 19. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 6 có tất cả 3 số nguyên tố là: 2, 17, 11; nên tổng 3 số trên là 30.

Yêu cầu: Cho dãy gồm có ~N~ số nguyên, ứng với mỗi cặp số ~x~, ~y~ hãy in ra tổng các số nguyên tố từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~1≤N,q≤10^5~).
• Dòng 2: ghi giá trị dãy số ~a_1,a_2,…a_N~ (~1≤a_i≤10^6~) các số cách nhau một dấu cách.
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên (~1 ≤ x \le y \le N~).

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là tổng các số nguyên tố từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

7 3
1 3 5 6 8 9 11
1 3
2 6
3 7

Output

8
8
16

Người ta định nghĩa số chính phương là số bằng bình phương của 1 số tự nhiên. Ví dụ: 16 là số chính phương vì ~16 = 4^2~, còn 15 không phải là số chính phương. Cho 2 số nguyên dương P, Q ~(0 < P \le Q \le 2.10^9)~

Yêu cầu: Đếm số lượng các số chính phương nằm trong đoạn [P,Q].

Input:

• Dòng 1: Chứa 2 số P,Q cách nhau ít nhất một dấu cách.

Output:

• Dòng 1: Ghi một số nguyên là số lượng các số chính phương.

Example:

Input:

1 10

Output:

3

Số T-Prime là số có đúng 3 ước. Cho số nguyên dương ~N~. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số liên tiếp từ 1 đến N có bao nhiêu số T-Prime. Ví dụ: Cho N=40, x=3, y =30, dãy số từ 1 đến 40. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 30 có tất cả 2 số T-Prime là: 9 và 25.

Yêu cầu: Cho số nguyên dương ~N~, ứng với mỗi cặp số ~x~, ~y~ hãy in ra số lượng các số T-Prime từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~1 ≤ N \le 10^7~, ~q≤10^5~).
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên(~1≤ x \le y \le N~).

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là số lượng các số T-Prime từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

40 3
1 3
1 30
3 10

Output

0
3
2

Số T-Prime là số nguyên dương có đúng 3 ước số nguyên dương khác nhau. Ví dụ 49 là số T-Prime vì 49 có đúng 3 ước số nguyên dương là 1, 7, 49.

Yêu cầu: Cho trước số nguyên dương ~N~ (~0 < N ≤ 10^6~) và dãy gồm ~N~ số nguyên dương ~a_1, a_2,...a_N~ (~0 \le a_i \le 10^{10}~).Hãy đếm xem có bao nhiêu số T-Prime trong dãy.

Dữ liệu vào:

• Dòng thứ nhất: Ghi số nguyên ~N~.
• Dòng 2: Ghi ~N~ số nguyên ~a_1, a_2,...a_N~

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input

8
3 4 5 9 36 49 55 121

Output

4

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Nam đố Quân bài toán sau: Cho dãy số gồm các số nguyên dương. Đếm dãy số đó có bao nhiêu số nguyên tố. Ví dụ dãy số 3, 6, 2, 17, 11, 22, 19 có các số nguyên tố sau: 3, 2, 17, 11, 19.

Yêu cầu: cho dãy số gồm có n phần tử đếm xem trong dãy số đó có bao nhiêu số nguyên tố.

Dữ liệu vào:

• Dòng đầu ghi số ~n~ (~0≤n≤1000~).
• Dòng tiếp theo ghi giá trị dãy số ~a_1,a_2,…a_n~ (~1≤a_i≤10^9~) các số cách nhau một dấu cách.

Kết quả:

• Ghi số lượng số nguyên tố. Không có số nào thì ghi -1.

Ví dụ:

Input

10
3 10 2 11 6 8 17 19 65 10

Output

5

Sau tiết học tìm hiểu về số nguyên tố, giờ ra chơi Việt và Nam là 2 người bạn cùng ngồi chung 1 bàn đã cùng nhau suy nghĩ để giải một bài toán cô giáo vừa giao như sau: Tìm tất cả các cách để phân tích một số nguyên dương N thành tổng 2 số nguyên tố. Với số N nhỏ, Việt và Nam đã thực hiện tốt, tuy nhiên khi thực hiện bài toán với N lớn thì chưa thực hiện được. Em hãy giúp 2 bạn giải quyết bài toán trên.

Yêu cầu: Tìm K là số cách phân tích số N thành tổng 2 số nguyên tố.

Input:

Cho trong tệp văn bản NGUYENTO.INP có cấu trúc:

• Dòng 1: Ghi số nguyên dương N ~(N < 3.10^7)~

Output:

Ghi ra tệp văn bản NGUYENTO.OUT với cấu trúc:

• Dòng 1: Ghi số K.

Example:

Input:

10

Output:

2

Giải thích: Có 2 cách phân tích số 10 thành tích 2 số nguyên tố là: 3+7 và 5+5

Số nguyên dương N được gọi là số hoàn hảo nếu tổng các ước số dương nhỏ hơn N của N bằng chính nó. Ví dụ: 6 là số hoàn hảo vì 6 có 3 ước số dương nhỏ hơn 6 là 1; 2; 3 và 1 + 2 + 3 = 6. Cho hai số nguyên dương P và Q.

Yêu cầu: Liệt kê tất cả các số hoàn hảo nằm trong đoạn [P, Q].

Input:

• Nhập vào 2 số nguyên P, Q hai số được ghi cách nhau ít nhất một dấu cách

Output:

• Ghi các số hoàn hảo tìm được, các số được ghi cách nhau ít nhất một dấu cách và theo thứ tự tăng dần của giá trị. Nếu không có số hoàn hảo nào thì ghi ra số 0.

Example:

Input:

2 30

Output:

6 28

Constraints:

~0 < P < Q \le 10^{10}~

Một số được gọi là phong phú khi và chỉ khi tổng các ước số của số đó (không kể chính nó) lớn hơn số đó. Ví dụ, số ~12~ có tổng các ước số (không kể 12) là ~1 + 2 + 3 + 4 + 6 = 16 > 12~. Do đó ~12~ là một số phong phú.

Yêu cầu: Cho 2 số nguyên dương P và Q. Hãy đếm tất cả các số phong phú trong đoạn từ ~P~ đến ~Q~.

Input:

• Dòng 1: Ghi 2 số nguyên dương ~P,Q~ (~1 \le P,Q \le 10^6~)

Output:

• Dòng 1: Ghi một số nguyên duy nhất là số lượng các số phong phú tìm được trong dãy.

Example:

Input:

1 14

Output:

1

Yêu cầu:

Cho 1 dãy số nguyên gồm ~n~ số cho trước. Hãy đếm tất cả các số chính phương, nguyên tố, hoàn hảo, phong phú trong dãy.

Giải thích:

• Ước thực sự của 1 số là tập hợp tất cả các ước dương nhỏ hơn nó.
• Số chính phương là số có căn bậc 2 của nó là một số nguyên.
• Số nguyên tố là số chỉ có 2 ước là 1 và chính nó.
• Số hoàn hảo là số có tổng các ước thực sự của nó bằng chính nó. Ví dụ, số 6 có tổng các ước số (không kể 6) là 1 + 2 + 3 = 6. Do đó 6 là một số hoàn hảo.
• Số phong phú là số có tổng các ước thực sự của số đó lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 = 16 > 12. Do đó 12 là một số phong phú.

Input:

• Dòng 1: Ghi số nguyên 𝑛 ~(1 \le n \le 10^6)~
• Dòng 2: Ghi 𝑛 số nguyên ~A_1, A_2,...,A_n, 1 \le A_i \le 10^6~

Output:

• Dòng 1: Ghi 4 số nguyên dương lần lượt là số lượng các số chính phương, nguyên tố, hoàn hảo, phong phú tìm được trong dãy.

Example:

Input:

7
2 3 5 7 12 8 6

Output:

0 4 1 1

Cho số nguyên dương ~N~ (~1 \le N \le 10^{12}~).

Yêu cầu: Đếm các số chia hết cho 3 nhưng không chia hết cho 7 trong đoạn từ 1 đến ~N~.

Dữ liệu vào:

• Gồm 1 dòng duy nhất ghi số nguyên dương ~N~.

Dữ liệu ra:

• Ghi số nguyên dương ~T~ là kết quả bài toán.

Ví dụ:

Input

15

Output

5

Cho dãy số sau: 1 3 6 10 15 21 28...

Yêu cầu: Hãy tìm số hạng thứ ~N~ của dãy trên.

Dữ liệu vào:

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

Dữ liệu ra:

• Số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input

6

Output

21

Cho dãy số sau: 2 6 12 20 30 42..

Yêu cầu: Hãy tìm số hạng thứ ~N~ của dãy trên.

Dữ liệu vào:

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

Dữ liệu ra:

• Số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Input

5

Output

30

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó.

Yêu cầu: cho dãy số gồm có n phần tử hãy tìm ước nguyên tố lớn nhất của từng phần tử trong dãy đã cho.

Dữ liệu vào:

• Dòng đầu ghi số ~n~ (~0≤n≤10^6~).
• Dòng tiếp theo ghi giá trị dãy số ~a_1,a_2,…a_n~ (~1≤a_i≤10^6~) các số cách nhau một dấu cách.

Kết quả:

• Gồm 1 dòng ghi lần lượt các ước nguyên tố tương ứng của từng phần tử trong dãy.

Ví dụ:

Input

10
2 3 6 9 10 11 13 17 23 22

Output

2 3 3 3 5 11 13 17 23 11

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó.

Yêu cầu: Cho dãy số gồm có n phần tử hãy tìm ước nguyên tố bé nhất của từng phần tử trong dãy đã cho.

Dữ liệu vào:

• Dòng đầu ghi số ~n~ (~0≤n≤10^6~).
• Dòng tiếp theo ghi giá trị dãy số ~a_1,a_2,…a_n~ (~1≤a_i≤10^6~) các số cách nhau một dấu cách.

Kết quả:

• Gồm 1 dòng ghi lần lượt các ước nguyên tố tương ứng của từng phần tử trong dãy.

Ví dụ:

Input

10
2 3 6 9 10 11 13 17 23 22

Output

2 3 2 3 2 11 13 17 23 2

Trên đường đi học về An đi qua một con phố có N ngôi nhà được đánh số từ 1 đến N. Những ngôi nhà bên trái của dãy phố được đánh số lẻ, ở bên phải được đánh số chẵn. An vừa đi vừa nhìn sang bên trái và sang phải rồi tính nhẩm tổng các số nhà ở hai bên con phố.

Yêu cầu: Em hãy giúp An tính tổng các số nhà ở dãy bên phải và bên trái con phố?

Input:

• Nhập vào số nguyên dương N.

Output:

• Dòng 1: Chứa số nguyên dương K là tổng các số nhà được đánh số lẻ.
• Dòng 2. Chứa số nguyên M là tổng các số nhà được đánh số chẵn.

Example:

Input:

10

Output:

25
30

Constraint:

~0 < N \le 10^9~

Số chính phương là số tự nhiên mà có thể viết dưới dạng bình phương của một số tự nhiên khác. Ví dụ: ~0, 1, 4, 9, 16, 25, …~ là các số chính phương, còn các số ~2, 3, 5, …~ không là số chính phương.

Yêu cầu: Cho dãy gồm ~𝑛~ số nguyên ~𝑎_1,𝑎_2, … , 𝑎_𝑛~. Tìm số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~𝑛~ (~1 ≤ 𝑛 ≤ 10^6~);
• Dòng thứ hai chứa ~𝑛~ số nguyên ~𝑎_1,𝑎_2, … , 𝑎_𝑛~ (~0 ≤ 𝑎_𝑖 ≤ 10^{12}, 𝑖 = 1, 2, … , 𝑛~), các số cách nhau một dấu cách.

Dữ liệu ra:

• In ra màn hình kết quả tìm được.

Ví dụ:

Input

8
0 3 4 2 1 4 16 25

Output

9

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm của câu có ~1 ≤ 𝑛 ≤ 10^3, 0 ≤ 𝑎_𝑖 ≤ 10^4~;
• Có 30% số test tương ứng với 30% số điểm của câu có ~10^3 < 𝑛 ≤ 10^6, 0 ≤ 𝑎_𝑖 ≤ 10^6~;
• Có 20% số test tương ứng với 20% số điểm của câu có ~0 ≤ 𝑎_𝑖 ≤ 10^{12}~;

Số T-Prime là số nguyên dương có đúng 3 ước số nguyên dương khác nhau. Ví dụ 49 là số T-Prime vì 49 có đúng 3 ước số nguyên dương là 1, 7, 49.

Yêu cầu: Cho trước số nguyên dương ~N~ (~0 < N ≤ 10^{14}~). Hãy in ra các số T-Prime không vượt quá ~N~.

Dữ liệu vào:

• Dòng thứ nhất: Ghi số nguyên ~N~.

Dữ liệu ra:

• Hãy in ra các số T-Prime không vượt quá ~N~.

Ví dụ:

Input

100

Output

4 9 25 49

Giải thích:

• Các số 4, 9, 25, 49 là số có 3 ước số

Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Nam đố Quân bài toán sau: Cho dãy số gồm ~N~ số nguyên dương, các số trong dãy được đánh số bắt đầu từ 1. Tính tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy đã cho. Ví dụ: Cho N=7, x=3, y =6, dãy số 3, 6, 2, 17, 11, 22, 19. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 6 có tất cả 3 số nguyên tố là: 2, 17, 11; nên tổng các số nguyên tố có trong đoạn từ 3 đến 6 là: 30

Yêu cầu: Cho dãy gồm có ~N~ số nguyên, ứng với mỗi cặp số ~x~, ~y~ hãy tính tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~0≤N,q≤10^5~).
• Dòng 2: ghi giá trị dãy số ~a_1,a_2,…a_N~ (~1≤a_i≤10^7~) các số cách nhau một dấu cách.
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên.

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy trên.

Ví dụ:

Input

7 3
1 3 5 6 8 9 11
1 3
2 6
3 7

Output

8
8
16