Một số i > 1 được gọi là "số lũy thừa" nếu nó chỉ có duy nhất một ước nguyên tố. (Ví dụ: 8 = 2^3, 9 = 3^2, 5 = 5^1). Cho N. Hãy đếm số lượng "số lũy thừa" i (1 < i <= N).

Input:

Một dòng duy nhất chứa số nguyên N (2 <= N <= 1000000).

Output:

In ra số lượng số lũy thừa.

Test Case 1:

Input:

20

Output:

12

(Giải thích: {2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19})

Một số được gọi là "Square-Free" nếu nó không chia hết cho bất kỳ số chính phương nào lớn hơn 1. Cho Q truy vấn, hãy kiểm tra xem n có phải là Square-Free hay không.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng sau chứa n.

Dữ liệu ra: In ra "YES" nếu n là Square-Free, ngược lại in "NO".

Ràng buộc: 1 <= Q <= 100000 1 <= n <= 1000000

Ví dụ 1:

Input:

3 
10 12 1

Output:

YES 
NO 
YES

Ví dụ 2:

Input:

2 18 7

Output:

NO 
YES

Một số được coi là đẹp nếu nó là số nguyên tố và tổng chữ số là một số trong dãy Fibonaci. Viết chương trình liệt kê trong một đoạn giữa hai số nguyên cho trước có bao nhiêu số đẹp như vậy.

INPUT:

2 50

OUTPUT:

2 3 5 11 17 23 41

Cho T truy vấn. Với mỗi số X, hãy in ra tất cả các thừa số nguyên tố của X (bao gồm cả lặp lại). Ví dụ: 12 -> 2 2 3.

Input:

Dòng đầu tiên chứa T (1 <= T <= 100000).

T dòng tiếp theo, mỗi dòng chứa một số nguyên X (2 <= X <= 1000000).

Output:

T dòng, mỗi dòng là danh sách các thừa số nguyên tố, cách nhau bởi dấu cách.

Test Case 1:

Input:

3
30
12
17

Output:

2 3 5
2 2 3
17

Cho n số nguyên dương, hãy tinh bội chung nhỏ nhất của n số đó.

Input:

• Dòng thứ nhất gồm một số nguyên dương n (n ≤ 50).

• Dòng thứ hai gồm n số nguyên dương có giá trị không vượt quá 30.

Output:

• In ra bội chung nhỏ nhất của n số đã cho.

Input:

5
3 6 2 9 5

Output:

90