Đếm ước qua điều kiện GCD

Trong một buổi concert, FullHouse Dev được khán giả yêu cầu giải một bài toán thú vị. Họ cần phải tìm ra số lượng các số nguyên thỏa mãn một số điều kiện đặc biệt.

Bài toán

Cho một số nguyên dương \(n\). Với \(q\) truy vấn, bạn cần xác định số lượng các số nguyên \(c\) (\(1 \leq c \leq n\)) sao cho \(gcd(c,n) = c\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(q\) - số lượng truy vấn
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\)

OUTPUT FORMAT:

• In ra \(q\) dòng, mỗi dòng chứa một số nguyên là đáp án cho truy vấn tương ứng

Ràng buộc:

• \(1 \leq q \leq 10^5\)
• \(1 \leq n \leq 10^9\)

Ví dụ

INPUT

1
10

OUTPUT

3