#include <cstdio>

int n;

int phi(int n) {
    int ans=1;
    for (int i=2;i*i<=n;i++) if (n%i==0) {
        ans*=i-1;
        n/=i;
        while (n%i==0) {
            ans*=i;
            n/=i;
        }
    }
    if (n!=1) ans*=n-1;
    return ans;
}
int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&n);
        printf("%d\n",phi(n+1));
    }
    return 0;
}