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