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 = 42, 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:

Cho trong file văn bản SOCP.INP có cấu trúc như sau:

• 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ố chính phương được định nghĩa là bình phương của một số nguyên.

Yêu cầu: Với số n cho trước, hãy tính tổng các số chính phương trong đoạn từ 1 đến n.

Input

• Dòng đầu tiên chứa q ~(q \le 10^4)~ - số truy vấn.
• q dòng tiếp mỗi dòng chứa số nguyên dương n ~(n \le 10^{18})~

Output

• Mỗi dòng chứa tổng S sau khi đã mod cho ~10^9 + 7~

Example

Input:

1
1

Output:

1

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ố trong xâu được hiểu là tập hợp các ký tự số đứng liền nhau: Ví dụ: ~S='nb234nm76nm8'~ có 3 số xuất hiện trong xâu ~S~ là: 234, 76,8. Cho xâu ký tự ~S~ được đọc ra từ tệp .

Yêu cầu: Tìm số chính phương lớn nhất không xuất hiện trong xâu, biết rằng các số xuất hiện trong xâu có không quá 9 chữ số và số chính phương lớn nhất tìm được phải nhỏ hơn số lớn nhất trong xâu.

Input:

• Nhập vào một xâu ký tự ~S~.

Output:

• In ra số chính phương lớn nhất không xuất hiện trong xâu s theo yêu cầu trên.

Example:

Input:

nb2nm76nm8j3733

Output:

3721

Constraints:

~0 < length(S) \le 10^6~

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

Một số nguyên dương ~N~ được gọi là một số siêu nguyên tố nếu ~N~ là số nguyên tố và khi ta bỏ bao nhiêu chữ số tận cùng của ~N~ thì số tự nhiên mới tạo thành cũng là một số nguyên tố.

Ví dụ:

Số 317 là số siêu nguyên tố vì số 317 là số nguyên tố, số 31 (bỏ 1 chữ số tận cùng của 317) là số nguyên tố, số 3 (bỏ 2 chữ số tận cùng của 317) là số nguyên tố. Số 61 không là số siêu nguyên tố vì số 6 (bỏ 1 chữ số tận cùng của 61) không là số nguyên tố.

Yêu cầu: Viết chương trình nhập vào từ bàn phím một số nguyên dương ~N~ (~0 < N \le 10^9~) và in ra màn hình một từ khẳng định số ~N~ có phải là số siêu nguyên tố hay không.

Input

• Số nguyên dương ~N~.

Output

• In ra màn hình một từ PHAI nếu ~N~ là số siêu nguyên tố; ngược lại, in ra mànhình một từ KHONG nếu ~N~ không phải là số siêu nguyên tố.

Ví dụ

Input1

317

Output1

PHAI

Input2

61

Output2

KHONG

Cho số nguyên dương ~n~, khi đảo ngược trật tự các chữ số của n ta sẽ thu được một số nguyên dương ~m~, ~m~ được gọi là số đảo ngược của ~n~. Ví dụ: ~n = 613~ thì ~m= 316~ là số đảo ngược của ~n~. Số nguyên dương m được gọi là số nguyên tố nếu nó chỉ có hai ước số là 1 và chính nó, số 1 không phải là số nguyên tố. Cho hai số nguyên dương p và q với ~0 < p < q ≤ 10^6~.

Yêu cầu: Hãy tìm tất cả các số nguyên dương n thỏa mãn ~p ≤ n ≤ q~ mà số đảo ngược của số n là số nguyên tố.

Dữ liệu vào:

• Một dòng ghi hai số nguyên dương ~p~,~q~.

Kết quả:

• Gồm nhiều dòng, mỗi dòng ghi một số nguyên n tìm dược.

Example

Input:

10 19

Output:

11
13
14
16
17

Số nguyên tố là số nguyên dương chỉ có duy nhất hai ước là 1 và chính nó. Ví dụ: số 11 là số nguyên tố vì nó chỉ có hai ước là 1 và 11; số 15 không phải số nguyên tố vì nó có 4 ước gồm 1, 3, 5 , 15; số 1 không phải là số nguyên tố vì nó có 1 ước là 1.

Yêu cầu: Cho số nguyên ~N~ (~1 ≤ N ≤ 2.10^5~) và N đoạn số nguyên (~1 ≤ L_i ≤ R_i ≤ 10^7~). Hãy tìm số lượng số nguyên tố thuộc mỗi đoạn

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~N~.
• ~N~ dòng tiếp theo, dòng thứ i chứa hai số nguyên(ngăn cách nhau bởi một khoảng trắng)

Dữ liệu ra:

-Gồm ~N~ dòng, dòng thứ i ghi một số nguyên là số lượng số nguyên tố thuộc đoạn .

Ví dụ:

Input

2
14 16
11 25

Output

0
5

Ràng buộc:

• Có 40% số test tương ứng 40% số điểm của bài với ~1 \le N \le 10^3; 1 \le L \le R \le 10^3~
• Có 60% số test tương ứng 60% số điểm của bài với ~10^3 < N \le 2.10^5; 1 \le L \le R \le 10^7~.

Cho một số nguyên dương ~N~, kiểm tra ~N~ có phải là tích của 2 hay nhiều số tự nhiên bất kì hay không?

2 số bất kì này khác N

Nếu không phải hãy in ra 'AC' ngược lại hãy in ra 'WA'

Dữ liệu vào:

• Dòng 1: Số nguyên dương ~N~ (~N \le 4.10^{16}~)

Dữ liệu ra:

• Dòng 1: Yêu cầu của bài toán

Ràng buộc

• 60% số test: ~N \le 10^{8}~
• 40% số test: không có ràng buộc gì thêm

Example

Input

7

Output

AC

Input

9

Output

WA

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^{12}~

Số trong xâu được hiểu là tập hợp các ký tự số đứng liền nhau: Ví dụ: ~S='nb234nm76nm8'~ có 3 số xuất hiện trong xâu ~S~ là: 234, 76,8. Cho xâu ký tự ~S~ được đọc ra từ tệp .

Yêu cầu: Tìm số hoàn hảo lớn nhất xuất hiện trong xâu, biết rằng các số xuất hiện trong xâu có không quá 10 chữ số.

Input:

• Nhập vào một xâu ký tự ~S~.

Output:

• In ra số hoàn hảo lớn nhất xuất hiện trong xâu s. Nếu trong xâu không xuất hiện số hoàn hảo thì ghi -1.

Example:

Input:

nb2nm76nm8j8128

Output:

8128

Constraints:

~0 < length(S) \le 10^5~

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

Định nghĩa: Số "tương lai" là số có các ước (không kể 1 và chính nó) là các số nguyên tố. Ví dụ: 10 có 2 ước thực sự là 2 và 5 là các số nguyên tố nên 10 là số "tương lai".

Yêu cầu: Cho dãy số nguyên ~A_1~ , ~A_2~ ,….., ~A_N~ (~1 \le N \le 10^4~ với mọi i sao cho ~1 \le A_i \le 10^6~). Hãy cho biết trong dãy trên có bao nhiêu số tương lai. Số tương không bao gồm các số nguyên tố.

Input:

• Dòng thứ nhất gồm số nguyên N. • Dòng thứ hai gồm các số ~A_1~, ~A_2~,…..,~A_N~ .

Output:

• Số lượng số tương lai thỏa đề.

Example:

Input:

9
9 7 10 6 17 4 19 21 13

Output:

5

Một số nguyên dương ~N~ được gọi là số hạnh phúc khi nó có ~2k~ chữ số và tổng k chữ số đầu bằng k chữ số cuối(~0 < k < 9~). Ví dụ: ~N=1946~ là số hạnh phúc.

Yêu cầu: Viết chương trình nhập vào số nguyên dương ~N~ và dãy gồm ~N~ số nguyên(~0<N<1000; 0\le a_i<2.10^{18}~). Sau đó: In ra các số hạnh phúc có trong dãy vừa nhập, nếu trong dãy không có số hạnh phúc nào thì in -1.</p>

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương N (~10 \le N \le 1000~).
• Dòng 2: Ghi ~N~ số nguyên ~a_1, a_2,….a_N~ (~10 \le a_i \le 2*10^{18}~)

Dữ liệu ra:

• Dòng 1 ghi ra các số hạnh phúc có trong dãy. Mỗi số cách nhau bởi dấu cách.

Ví dụ:

Input

7
34 43 1234 1340 3223 1234554321 5678

Output

1340  3223 1234554321

Số tự mãn là những số bằng tổng các lũy thừa các chữ số với số mũ bằng số các chữ số của nó.

Ví dụ:

~153 = 1 ^ 3 + 5 ^ 3 + 3 ^ 3~

~8208 = (8 * 8 * 8 * 8) + (2 * 2 * 2 * 2) + (0 * 0 * 0 * 0) + (8 * 8 * 8 * 8)~

Yêu cầu: Kiểm tra 1 số nguyên dương ~n~ có phải là số tự mãn hay không.

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương ~𝑛~ (~1 ≤ 𝑛 ≤ 32000~)

Dữ liệu ra:

• Dòng 1: Ghi 'YES' nếu n là số tự mãn, ngược lại ghi 'NO'.

Ví dụ:

Input

8208

Output

YES

Cho số nguyên tố X, nhiệm vụ của bạn là đếm xem trong đoạn từ 1 đến ~10^6~, có bao nhiêu số mà khi phân tích số đó ra thừa số nguyên tố thì thừa số nguyên tố nhỏ nhất là ~X~.

Input

● Dòng đầu tiên chứa 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 tố ~X~

Output

• Với mỗi số nguyên tố ~X~, ghi ra một số nguyên duy nhất là số lượng số khi phân tích ra thừa số nguyên tố thì giá trị nguyên tố nhỏ nhất là ~X~, kết quả ghi ra trên mỗi dòng.

Ràng buộc

● ~1 \le T \le 10^6~ ● ~2 \le X \le 10^6~

Ví dụ

Input

2
2
11

Output

500000
20779

Hợp số là số nguyên dương lớn hơn 1 và có nhiều hơn 2 ước.

Yêu cầu: Hãy kiểm tra ~N~ số nguyên ~a_1, a_2,.., a_N~ có phải là hợp số hay không?

Dữ liệu vào:

Đọc dữ liệu từ file HOPSO.INP có cấu trúc như sau:

• Dòng 1 gồm 1 số nguyên dương ~N~ (~N ≤ 10^5~)
• N tiếp theo ghi các số nguyên ~a_1, a_2,.., a_N~ (~0 < a_i ≤ 10^5~)

Dữ liệu ra:

Ghi vào file HOPSO.OUT gồm:

• ~N~ dòng, nếu ~a_i~ là hợp số thì ghi 1, nếu ~a_i~ không phải là hợp số ghi số 0.

Ví dụ:

input

3
1
3 
16

Output

0
0
1