Cho một số nguyên N , hãy đếm có bao nhiêu số nguyên dương i không vượt quá N sao cho GCD(i, N) = 1.

Lưu ý: GCD(a, b) = c với c là số nguyên dương lớn nhất mà a và b đều chia hết cho c.

Dữ liệu

• Dòng đầu tiên chứa 1 số nguyên T là số lượng test (1 ≤ T ≤ 10).

• T dòng tiếp theo, mỗi dòng chứa một số nguyên N (1 ≤ N ≤ 10⁹) Kết quả

Gồm T dòng, mỗi dòng chứa kết quả bài toán ứng với mỗi test case.

Ví dụ:

• Subtask 1 (50% số điểm): 1 ≤ N ≤ 10⁵.

• Subtast 2 (50% số điểm): không có giới hạn gì thêm.