Một số được gọi là T-prime nếu nó có đúng 3 ước số. Hãy đếm số lượng số T-prime không vượt quá N.

Dữ liệu vào:

Dòng 1: N (1 <= N <= 10^12).

Dữ liệu ra:

Số lượng số T-prime.

Ví dụ:

Input:

10

Output:

2

Giải thích: 4 (1,2,4), 9 (1,3,9)

Đề bài: Cho số nguyên N và K. Hãy đếm số lượng ước của N mà không chia hết cho K.

Dữ liệu vào:

Dòng 1: Q (1 <= Q <= 10^5).

Mỗi dòng: N, K (1 <= N, K <= 10^6).

Dữ liệu ra:

Kết quả.

Ví dụ:

Input:

1 
12 2

Output:

2

Giải thích: Ước của 12 là 1, 2, 3, 4, 6, 12. Các ước không chia hết cho 2 là 1, 3.

Số thịnh vượng (Abundant Number) là một số nguyên dương mà tổng các ước số thực sự của nó (các ước nhỏ hơn chính nó) lớn hơn chính nó.

Ví dụ:

Số 12 có các ước số thực sự là 1, 2, 3, 4, 6. Tổng các ước là 1 + 2 + 3 + 4 + 6 = 16. Vì 16 > 12 nên 12 là số thịnh vượng.

Số 10 có các ước số thực sự là 1, 2, 5. Tổng các ước là 1 + 2 + 5 = 8. Vì 8 < 10 nên 10 không phải là số thịnh vượng.

Cho Q câu hỏi, mỗi câu hỏi gồm một số nguyên N. Hãy kiểm tra xem N có phải là số thịnh vượng hay không.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên Q là số lượng truy vấn.

Q dòng tiếp theo, mỗi dòng chứa một số nguyên dương N cần kiểm tra.

Dữ liệu ra:

Với mỗi giá trị N, in ra "YES" nếu N là số thịnh vượng, in ra "NO" nếu không phải. (Mỗi kết quả trên một dòng).

Giới hạn:

1 <= Q <= 10^6

1 <= N <= 10^6

Thời gian chạy: 1 giây

Ví dụ:

Input:

3 
12 
10 
18

Output:

YES 
NO 
YES

Cho Q truy vấn n. Tính tổng các số nguyên dương k <= n sao cho GCD(k, n) = 1.

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

Dữ liệu ra: Q dòng kết quả.

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

Ví dụ 1:

Input:

2 5 10

Output:

10 20

Ví dụ 2:

Input:

1 4

Output:

4

Cho số nguyên n. Hãy tính tổng S = GCD(1, n) + GCD(2, n) + ... + GCD(n, n). Vì n có thể lớn, bài toán yêu cầu xử lý nhiều truy vấn.

Dữ liệu vào: Dòng đầu chứa Q. Q dòng tiếp theo, mỗi dòng chứa n.

Dữ liệu ra: Q dòng, mỗi dòng là kết quả tổng S.

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

Ví dụ 1:

Input:

2 5 6

Output:

9 15

Ví dụ 2:

Input:

1 10

Output:

27

Cho Q truy vấn, mỗi truy vấn là một số n. Hãy tính Phi(n) - số lượng các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n.

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

Dữ liệu ra: Q dòng, mỗi dòng là giá trị Phi(n).

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

Ví dụ 1:

Input:

2 10 7

Output:

4 6

Ví dụ 2:

Input:

2 1 12

Output:

1 4