#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int M=1000010;

int euler[M];

void Init()
{
    euler[1] = 1;
    for (int i = 2; i<1000005; i++)
        euler[i] = i;
    for (int i = 2; i<1000005; i++)
        if (euler[i] == i)
            for (int j = i; j<1000005; j += i)
                euler[j] = euler[j] / i*(i - 1);
}

int main()
{
    Init();
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        printf("%d\n", euler[n+1]);
    }
    return 0;
}