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

见题面

见题面