Hệ thống ngân hàng XYZ sử dụng một thuật toán mã hóa khóa công khai. Để kích hoạt hệ thống, kỹ sư cần nhập vào một "Mã khóa".

Cho một số nguyên dương N. "Mã khóa" của N được định nghĩa là số lượng các số nguyên dương X sao cho:

1 <= X <= N và GCD(X, N) = 1. (lưu ý số nguyên tố cùng nhau với 1 là 1)

Vì N có thể rất lớn, hãy lập trình để tính nhanh "Mã khóa" này.

Input:

• Dòng 1: Số nguyên T (1 <= T <= 100) là số lượng bộ test.

• T dòng tiếp theo: Mỗi dòng chứa một số nguyên dương N (1 <= N <= 10^14).

Output:

• Với mỗi giá trị N, in ra một số nguyên duy nhất là kết quả tìm được.

Ví dụ 1:

Input:

2
7
10

Output:

6
4

Giải thích:

• Với N=7, các số nguyên tố cùng nhau là: 1, 2, 3, 4, 5, 6 (Tổng 6 số).

• Với N=10, các số nguyên tố cùng nhau là: 1, 3, 7, 9 (Tổng 4 số).