exam-time-2_5032
Geeko is in worry now because exam is coming up and he has to know 
  what rank he can get in exams. So he go back into the school records
  and finds the amazing pattern. 
He finds that if a student is having a current rank n than his rank 
  in the final exam will be the count positive numbers between in the range [1,n] which are relatively prime to n 

 As being geek he became curious now he want to calculate the 
  rank of all his classmates in final exam, but he finds this task a bit hard
  , So he ask you programmers to solve this task for him.
Input: 
  The first line of each test file contains a integer t denoting the number of
  test case.Each test case contains a numbers n  representing
  the current rank of each student  
Output:
 for each test case output single integer the rank of student in final exam  in new line.
  
Constraints:
 1 ≤ t ≤ 2000 

   1 ≤ n <10^6
 

SAMPLE INPUT
2
5
4

SAMPLE OUTPUT
4
2
def main():
    from collections import defaultdict
    from itertools import count
    from fractions import gcd
    from operator import mul
    from sys import stdin,stdout
    
    def lcm(a, b): return a * b / gcd(a, b)
    
    primes_cache, prime_jumps = [], defaultdict(list)
    
    def primes():
        prime = 1
        for i in count():
            if i < len(primes_cache): prime = primes_cache[i]
            else:
                prime += 1
                while prime in prime_jumps:
                    for skip in prime_jumps[prime]:
                        prime_jumps[prime + skip] += [skip]
                    del prime_jumps[prime]
                    prime += 1
                prime_jumps[prime + prime] += [prime]
                primes_cache.append(prime)
            yield prime
            
    def factorize(n):
        for prime in primes():
            if prime > n: return
            exponent = 0
            while n % prime == 0:
                exponent, n = exponent + 1, n / prime
            if exponent != 0:
                yield prime, exponent
                
    def totient(n):
        return int(reduce(mul, (1 - 1.0 / p for p, exp in factorize(n)), n))
    
    t = int(stdin.readline())
    while t>0:
        n = int(stdin.readline())
        stdout.write(str(totient(n))+'\n')
        t-=1
        
if __name__=='__main__':
    main()