#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)j;i>=(int)k;i--)
using namespace std;
typedef long long LL;
typedef double db;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);n++;
        int ans=n;
        for(int i=2;i*i<=n;i++)if(n%i==0){
            ans=(ans/i)*(i-1);
            while(n%i==0)n/=i;
        }
        if(n>1)ans=(ans/n)*(n-1);
        printf("%d\n",ans);
    }
    return 0;
}