1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 using namespace std;

 7 typedef long long ll;

 8 const int maxn=100005;

 9 int oula(int n)

10 {

11     int ans=n;

12     for(int i=2; i<=sqrt(n); ++i)

13     {

14         if(n%i==0)

15         {

16             ans=ans-ans/i;

17             n/=i;

18             while(n%i==0)

19                 n/=i;

20         }

21     }

22     if(n>1)

23         ans=ans-ans/n;

24     return ans;

25 }

26 int main()

27 {

28     int t;

29     scanf("%d",&t);

30     while(t--)

31     {

32         int n;

33         scanf("%d",&n);

34         int result=oula(n);

35         printf("%d\n",result);

36     }

37     return 0;

38 }