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⁶
2 <= N <= 10⁷