Count of integers

★★★★★

3.7

18 votes

Algorithms, Euler's totient function, Greatest common divisor, Math, Number Theory, Sieve

Details

Problem

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$

Sample Input

1
10

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For c = {1,3,7,9} gcd(c,10) = 1

For c = {2,5,10} gcd(c,10) = c

gcd(4,10) = 2

gcd(6,10) = 2

gcd(8,10) = 2

So, answer is 3.

Contributers:

Tanmay Agrawal

Amirreza Poorakhavan