Cho số nguyên dương n. Hãy tính phi hàm Euler của n, ký hiệu là phi(n). Đây là số lượng các số nguyên dương m <= n sao cho gcd(m, n) = 1.

Dữ liệu vào: Một dòng duy nhất chứa số nguyên n.

Dữ liệu ra: Một dòng duy nhất chứa kết quả phi(n).

Ràng buộc: 1 <= n <= 10^12.

Ví dụ:

Input:

10

Output:

4

(Giải thích: Các số là 1, 3, 7, 9)

Mô tả: Trong đoạn [L, R], hãy tìm số x sao cho phi(x) là lớn nhất. Nếu có nhiều số cùng phi(x) lớn nhất, in ra số x nhỏ nhất.

Dữ liệu vào: Hai số nguyên L và R.

Dữ liệu ra: Số x thỏa mãn.

Ràng buộc: 1 <= L <= R <= 10^6.

Ví dụ:

Input:

1 5

Output:

5

(Giải thích: phi(1)=1, phi(2)=1, phi(3)=2, phi(4)=2, phi(5)=4)

Mô tả: Cho số nguyên dương n. Hãy tìm số nguyên dương x nhỏ nhất sao cho phi(x) = n. Nếu không tồn tại x, in ra -1.

Dữ liệu vào: Một số nguyên dương n.

Dữ liệu ra: Giá trị x nhỏ nhất hoặc -1.

Ràng buộc: 1 <= n <= 10^5.

Ví dụ:

Input:

4

Output:

5

(Giải thích: phi(5) = 4, phi(8) = 4, phi(10) = 4, phi(12) = 4. Nhỏ nhất là 5)

Một phân số a/b được gọi là phân số tối giản nếu 1 <= a < b <= n và gcd(a, b) = 1. Cho n, hãy đếm xem có bao nhiêu phân số tối giản như vậy.

Dữ liệu vào: Một dòng duy nhất chứa số n.

Dữ liệu ra: Số lượng phân số tối giản.

Ràng buộc: 1 <= n <= 10^6.

Ví dụ:

Input:

5

Output:

9

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

Mô tả: Cho số nguyên dương n. Hãy tính tổng S = phi(1) + phi(2) + ... + phi(n).

Dữ liệu vào: Một dòng duy nhất chứa số nguyên n.

Dữ liệu ra: Một dòng duy nhất chứa giá trị S.

Ràng buộc: 1 <= n <= 10^6.

Ví dụ:

Input:

3

Output:

4

(Giải thích: phi(1) + phi(2) + phi(3) = 1 + 1 + 2 = 4)

Cho T truy vấn, mỗi truy vấn là một số nguyên n. Hãy tính phi(n).

Dữ liệu vào:

Dòng đầu chứa số T là số lượng bộ test.

T dòng tiếp theo, mỗi dòng chứa một số nguyên n.

Dữ liệu ra: T dòng, mỗi dòng là kết quả của một truy vấn.

Ràng buộc: 1 <= T <= 10^5; 1 <= n <= 10^6.

Ví dụ:

Input:

2
1
6

Output:

1
2