You are given a positive integer \(n\), for \(Q\) queries, You are required to determine the number of integers \(k\) (\(1 \leq k \leq n\)) such that \(gcd(k,n)\hspace{2mm}!= 1\) and \(gcd(k,n)\hspace{2mm}!= k\).

Input format

• First line: Integer \(Q\) denoting the number of queries
• Next \(Q\) lines: Integer \(n\)

Output format

Print \(Q\) lines each containing an integer that denotes the answer to that specific query.

Constraints

\(1 \leq Q \leq 10^5\)

\(1 \leq n \leq 10^6\)