Viết chương trình nhập vào số nguyên dương N ~(0< N < 10^{12})~. Sau đó kiểm tra xem N có phải là số chính phương hay không? Nếu N là số chính phương thì ghi 'Yes' ngược lại ghi 'No'.

Example:

Input:

4

Input:

Yes

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

Nhập vào số nguyên dương ~N~(~1 \le N \le 10^5~) và dãy gồm ~N~ số nguyên ~A_1,A_2,A_3,...,A_N~ (~|A_i| \le 10^9~).

Yêu cầu: In ra các số chính phương có trong dãy vừa nhập. Số chính phương là số có căn bậc hai cũng là một số tự nhiên. Ví dụ: số 4 là số chính phương vì căn bậc 2 của 4 bằng 2.

Dữ liệu vào:

• Dòng 1: Số nguyên dương ~N~.
• Dòng 2: ghi ~N~ số nguyên ~A_1,A_2,A_3,...,A_N~.

Dữ liệu ra:

• Các số chính phương có trong dãy.

Ví dụ

Input

5
4 3 2 9 -5

Output

4 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}~;

Liệt kê các số chính phương dương và không vượt quá ~n~

Input Format

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

Constraints

~1≤n≤10^{10}~.

Output Format

• Liệt kê các số chính phương không vượt quá ~n~

Sample Input 0

50

Sample Output 0

1 4 9 16 25 36 49

Hãy tìm tất cả các số nguyên tố trong đoạn [A;B].

Input:

• Nhập vào 2 số nguyên A; B.

Output:

• Ghi ra tất cả các số nguyên tố trong đoạn [A;B]. Mỗi số trên 1 dòng.

Example:

Input:

1  10

Output:

2
3
5
7

Constraint:

~1 \le A \le B \le 10^7~

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

Cho một số nguyên dương N, hãy tính xem có bao nhiêu số nguyên dương bé hơn N và nguyên tố cùng nhau với N.

Input:

• Ghi số nguyên dương N.

Output:

• Ghi 1 số nguyên là kết quả của bài toán.

Example:

Input:

5

Output:

4

Constraints:

~0 < N \le 10^6~

Với một số nguyên dương n thì luôn tồn tại một cách phân tích n thành tích của các thừa số nguyên tố. Ví dụ: số 28 sẽ phân tích thành tích 2×2×7.

Yêu cầu: Cho số nguyên dương n, hãy phân tích n thành tích của các thừa số nguyên tố.

Input:

• Dòng đầu tiên: Ghi số nguyên dương n ~(2 ≤ n ≤ 2×10^9)~.

Output:

• Dòng đầu tiên: Ghi dãy số nguyên dương là các thừa số nguyên tố của n, các số được ghi theo thứ tự không giảm và cách nhau ít nhất một dấu cách.

Example:

Input:

28

Output:

2 2 7

Cho mảng số nguyên ~A[]~ gồm ~N~ phần tử, nhiệm vụ của bạn là tính trung bình cộng của các số là số nguyên tố trong dãy. Dữ liệu đảm bảo có ít nhất 1 phần tử là số nguyên tố trong dãy.

Input Format

• Dòng đầu tiên là số nguyên dương ~N~;
• Dòng thứ 2 gồm ~N~ số nguyên viết cách nhau một vài khoảng trắng.

Constraints

~1 \le N \le 1000; -10^3 \le A[i] \le 10^3~;

Output Format

• In ra đáp án của bài toán lấy 3 số sau dấu phẩy.

Sample Input 0

5
-911 234 151 347 231 

Sample Output 0

249.000

Sample Input 1

3 
1 2 5

Sample Output 1

3.500

Viết chương trình nhập vào 1 số nguyên dương N (~1 \le N \le 10^{12}~).

Input:

• Số nguyên dương N

Output

• In YES nếu N là số nguyên tố, ngược lại in NO

Example

Input

13

Output

YES

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ố được định nghĩa là một số nguyên dương chỉ có 2 ước 1 và chính nó. Cho số nguyên dương ~N~(~1 \le N \le 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^6~).

Yêu cầu: Đếm xem trong dãy trên có bao nhiêu số nguyên tố.

Input:

• Dòng 1. Ghi số nguyên dương ~N~.
• Dòng 2. Ghi N số nguyên dương ~A_1, A_2,...,A_N~

Output:

• Dòng 1. Gồm 1 số nguyên duy nhất là số lượng số nguyên tố tìm được.

Example:

Input

5
1 2 4 5 6

Output

2

Nhập vào ~n~ nguyên. Đếm số lượng chữ số của ~n~ là số nguyên tố.

Input Format

Số nguyên không âm ~n~

Constraints

~0≤n≤10^{18}~

Output Format

Kết quả của bài toán

Sample Input 0

1222333999888

Sample Output 0

6

Số nguyên dương N được gọi là số nguyên tố đối xứng nếu nó thỏa mãn 2 điều kiện sau:

• N là một số nguyên tố;
• N là một số đối xứng (số đối xứng là số mà khi đọc số đó từ trái qua phải thì cũng giống như khi đọc từ phải qua trái). Ví dụ: 12321 là một số đối xứng.

Yêu cầu:

• Kiểm tra số N có phải là số nguyên tố đối xứng hay không?

Dữ liệu vào:

• Dòng 1: Ghi số nguyên K là số dòng chứa dữ liệu cần kiểm tra (~0 < K ≤ 10~)

• ~K~ dòng tiếp theo, mỗi dòng ghi một số nguyên ~N~ (~0 < N ≤ 10^{12}~).

Kết quả:

• Ghi kết quả ra gồm K dòng, mỗi dòng ghi "Y" hoặc "N" tương ứng với số được kiểm tra là nguyên tố đối xứng hay không?

Ví dụ:

Input

2
101
12321

Output

Y
N

Số "siêu nguyên tố" được định nghĩa như sau: Là một số nguyên tố và tổng các chữ số của nó là một số nguyên tố. Ví dụ: Số ~131~ là số siêu nguyên tố vì ~131~ là một số nguyên tố và tổng các chữ số của nó là: ~1 + 3 + 1 = 5~ là một số nguyên tố.

Yêu cầu: Cho dãy gồm ~N~ số nguyên dương ~a_1, a_2,..., a_N~. Hãy lập trình in ra số lượng các số siêu nguyên tố trong dãy. Nếu trong dãy không có số nào là số siêu nguyên tố thì in ra ~0~.

Input

• Dòng đầu tiên là số nguyên duong ~N~ (~1 ≤ N ≤ 10^6~).

• Dòng tiếp theo ghi ~N~ số ~a_1, a_2,..., a_N~ (~1 ≤ a_i ≤ 10^6, với 1 ≤ i ≤ N~).

Output

• Một số duy nhất là số lượng số siêu nguyên tố có trong dãy.

Scoring

Có 40% số điểm ứng với các test có ~N ≤ 10^3; a_i ≤ 10^3~.

Có 30% số điểm ứng với các test có ~N ≤ 10^4; a_i ≤ 10^6~.

Có 30% số điểm ứng với các test có ~N ≤ 10^6; a_i ≤ 10^6~.

Examples

Input

5
31 12 131 22 151

Output

2

Input

5
17 9 18 15 16

Output

0

Note

• Ở ví dụ 1, có 2 số siêu nguyên tố là ~131~ và ~151~.

• Ở ví dụ 2, không có số siêu nguyên tố nào.

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

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 1 dãy số nguyên gồm n số cho trước. Hãy đếm tất cả các số phong phú trong dãy.

Input:

Được cho bởi tệp PHONGPHU.INP có cấu trúc như sau:

• 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 32000~

Output:

Được cho bởi tệp PHONGPHU.OUT có cấu trúc như sau:

• 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:

7
2 3 5 7 12 8 14

Output:

1

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:

Được cho bởi tệp dempp.inp có cấu trúc như sau:

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

Output:

Được cho bởi tệp dempp.out có cấu trúc như sau:

• 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

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ố đẹp là số có tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố. Ví dụ: 23 là một số đẹp vì ~2^2~  +  ~3^2~ là một số nguyên tố.

Dãy các số đẹp lần lượt là: ~11, 12, 14, 16, 21, 23, 25, 27, 32, 38~, ... . Các số đẹp được đánh số thứ tự tăng dần theo giá trị bắt đầu số thứ nhất là 11 , số thứ hai là 12, ...,  số thứ mười là 38.

Yêu cầu: Cho số nguyên dương ~N~ . Hãy tìm số đẹp thứ ~N~.

Input

• Chứa duy nhất một số nguyên ~N~ (~1 ≤ N ≤ 10000~).

Output

• Số đẹp thứ ~N~.

Scoring

• Subtask 1 (70%): ~N ≤ 10~;

• Subtask 2 (30%): Không ràng buộc gì thêm.

Examples

Input

1

Output

11

Input

6

Output

23

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~

Lam là học sinh có thành tích cao trong kỳ thi tuyển sinh vào lớp 10 chuyên Tin. Phần thưởng cho em là một phần mềm diệt virus. Mã số của phần mềm là một dãy gồm n số nguyên dương ~A_1, A_2, A_3, …A_n~ . Để cài đặt được phần mềm, Lam phải nhập vào mật khẩu của phần mềm. Mật khẩu là số lượng các số chia hết cho 90 của dãy số trên.

Yêu cầu: Hãy tìm mật khẩu để cài đặt phần mềm

Input

• Dòng 1: Ghi 1 số nguyên dương ~n~ (~1 ≤ n ≤ 10^3~).

• N dòng sau, dòng thứ i ghi số nguyên ~A_i~ (~1 ≤ A_i ≤ 10^{1000}~).

Output

• Duy nhất một số là mật khẩu tìm được

Examples

Input

4
90
10
90
27052023

Output

2

Input

1
9

Output

0

Trong buổi thi môn chuyên Tin học, sau khi trải qua hai bài đầu tiên của đề thi khá nhẹ nhàng, Tuyển bắt đầu gặp thử thách ở bài thứ 3. Ở bài này, Tuyển được giới thiệu về "Số tiến đẹp": là số nguyên dương có từ 2 chữ số trở lên, "tiến" nếu các chữ số từ trái sang phải tăng dần và "đẹp" nếu tổng các chữ số chia hết cho 9.

Yêu cầu: Cho số nguyên dương ~n~. Tuyển phải viết chương trình để cho biết số đó có phải là số tiến đẹp hay không?

Input

• Gồm 1 số nguyên dương n duy nhất (~1 ≤ n ≤ 10^9~).

Output

• In ra giá trị ~n~ nếu ~n~ là số tiến đẹp, ngược lại ỉn ra  - 1.

Examples

Input

235

Output

-1

Input

1224

Output

-1

Input

12357

Output

12357

Một số nguyên dương N được gọi là số đặc biệt nếu N chia hết cho tổng các chữ số của nó. Ví dụ, số 27 là số đặc biệt, còn hai số 11 và 2013 thì không phải là số đặc biệt.

Yêu cầu: Cho số nguyên dương N. Hãy kiểm tra xem số N có phải là số đặc biệt hay không?

Input:

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

Output:

• Nếu N là số đặc biệt in ra 1, nếu không phải in ra 0.

Example:

Input:

27

Output:

1

Constraints:

~0 < N \le 10^{18}~

Cho số nguyên dương N, hãy cho biết N có phải là số đối xứng hay không? Biết rằng số đối xứng là số có nếu đọc từ trái qua phải cũng có giá trị như dọc từ phải qua trái.

Input:

Được cho bởi tệp SODX.INP có cấu trúc như sau:

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

Output:

Được cho bởi tệp SODX.OUT có cấu trúc như sau:

• Dòng 1: Ghi số 0 nếu N không đối xứng, ngược lại in 1

Example:

Input:

12321

Output:

1

Ta gọi độ cao của một số nguyên dương K là tổng giá trị các chữ số của K. Ví dụ: số 18725 có độ cao là 23.

Yêu cầu: In ra độ cao của số nguyên dương N nhập từ bàn phím.

Input:

• Dòng 1: Chứa số nguyên dương N.

Output:

• Dòng 1: 1 số nguyên dương là kết quả bài toán.

Example:

Input:

456

Output:

15

Constraint:

~0 \le N \le 10^{18}~

Người ta quy định lổ hổng các số từ 0 đến 9 như sau, số có 1 vòng khép kín thì có 1 lổ hổng, chẳng hạn 0, 4, 6, 9; số 8 có 2 lổ hổng, các số còn lại không có lổ hổng nào. Ví dụ: số 18724, có 3 lổ hổng.

Yêu cầu: Nhập vào số nguyên dương N in ra số lổ hổng của N.

Input:

• Dòng 1: Chứa số nguyên dương N.

Output:

• Dòng 1: 1 số nguyên dương là kết quả bài toán.

Example:

Input:

456

Output:

2

Constraint:

~0 \le N \le 10^{18}~

Một số được gọi là số mạnh mẽ khi nó đồng thời vừa chia hết cho số nguyên tố và chia hết cho bình phương của số nguyên tố đó. Chẳng hạn, số 25 là số mạnh mẽ, vì nó vừa chia hết cho số nguyên tố 5, và bình phương của 5 (tức 25).

Yêu cầu: Hãy viết chương trình đếm tất cả các số mạnh mẽ trong đoạn từ ~1~ tới ~n~

Dữ liệu vào:

• Dòng 1: Chứa số nguyên dương ~n~ (~1 \le n \le 32000~).

Dữ liệu ra:

• Dòng 1: Ghi 1 số nguyên dương duy nhất là số lượng các số mạnh mẽ từ ~1~ tới ~n~.

Ví dụ:

Input

100

Output

39

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

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

Một số nguyên dương ~N~ được gọi là số bậc thang khi biểu diển thập phân của nó có từ 2 chữ số trở lên và chữ số đứng sau luôn lớn hơn chữ số đứng trước. Ví dụ: ~N=1346~ là số bậc thang.

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. Sau đó: In ra các số bậc thang có trong dãy vừa nhập, nếu trong dãy không có số bậc thang nào thì in -1.

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 32000~)

Dữ liệu ra:

• Dòng 1 ghi các số bậc thang có trong dãy.

Ví dụ:

Input

5
12 1232 12321 12357 123

Output

12 12357 123

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

Cho ~P~ là tập hợp các ước số dương không nguyên tố của số nguyên dương ~n~. Hãy tìm số phần tử của tập hợp ~P~.

Dữ liệu vào

• Một dòng duy nhất là giá trị của ~n~ (~1 ≤ n ≤ 10^{14}~)

Dữ liệu ra

• Một dòng duy nhất là số phần tử của ~P~

Ví dụ:

Input

20

Output

4

Input2

180

Output2

15

Đị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

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

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

Số N được gọi là số đẹp nếu số đó không chứa các chữ số 4 hoặc 7. Ví dụ N = 1368 là một số đẹp, còn N = 478 không phải là số đẹp.

Yêu cầu: Nhập vào số nguyên dương N, hãy kiểm tra xem N có phải là số đẹp hay ko.

Input:

• Ghi 1 số nguyên N.

Output:

• Nếu N là số đẹp thì in ra là 'YES' còn ngược lại thì in ra là 'NO'.

Example:

Input:

1368

Output:

YES

Constraints:

~0 < N \le 10^9~