eular-toitent-function-hard-1

Given an integer N. Find eular toitent function of N. Eular toitent function of N is total number of positive integers less than N which are co-prime to N. Two numbers A and B are said to be co-prime if their greatest common divisor is 1. For eg 4 and 5 are co-prime to each other but 4 and 6 are not co-prime.

Input 
First line contains T (number of test cases). 
Next T lines contains integer N.  
Constraints

1 ≤ T ≤ 2*10^6 
2 ≤ N ≤ 10^7

SAMPLE INPUT
3
4
7
10

SAMPLE OUTPUT
2
6
4

Source: hackerearth | Difficulty: MEDIUM


Solutions: