#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
int sfac[N];
void PF(int m, vector<int> &pf) {
int cur = m;
while (cur > 1) {
int p = sfac[cur];
pf.push_back(p);
while (cur % p == 0)
cur /= p;
}
}
int coprimes(int m) {
int res = m;
vector<int> pf;
PF(m, pf);
int n = pf.size();
for (int mask = 1; mask < (1 << n); ++mask) {
int mul = 1, ones = 0;
for (int i = 0; i < n; ++i)
if (((mask >> i) & 1) == 1) {
++ones;
mul *= pf[i];
}
if ((ones & 1) == 0)
res += m / mul;
else
res -= m / mul;
}
return res;
}
int main(int argc, char **argv) {
for (int p = 0; p < N; ++p)
sfac[p] = p;
for (int p = 2; p * p < N; ++p)
if (sfac[p] == p)
for (int q = p * p; q < N; q += p)
sfac[q] = min(sfac[q], p);
int T;
scanf("%d", &T);
while (T-- != 0) {
int m;
scanf("%d", &m);
int a = coprimes(m);
int b = m - 1;
printf("%lld\n", 1LL * a * b);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKCmNvbnN0IGludCBOID0gMWU2ICsgMTsKaW50IHNmYWNbTl07Cgp2b2lkIFBGKGludCBtLCB2ZWN0b3I8aW50PiAmcGYpIHsKCWludCBjdXIgPSBtOwoJd2hpbGUgKGN1ciA+IDEpIHsKCQlpbnQgcCA9IHNmYWNbY3VyXTsKCQlwZi5wdXNoX2JhY2socCk7CgkJd2hpbGUgKGN1ciAlIHAgPT0gMCkKCQkJY3VyIC89IHA7Cgl9Cn0KCmludCBjb3ByaW1lcyhpbnQgbSkgewoJaW50IHJlcyA9IG07Cgl2ZWN0b3I8aW50PiBwZjsKCVBGKG0sIHBmKTsKCWludCBuID0gcGYuc2l6ZSgpOwoJZm9yIChpbnQgbWFzayA9IDE7IG1hc2sgPCAoMSA8PCBuKTsgKyttYXNrKSB7CgkJaW50IG11bCA9IDEsIG9uZXMgPSAwOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQoJCQlpZiAoKChtYXNrID4+IGkpICYgMSkgPT0gMSkgewoJCQkJKytvbmVzOwoJCQkJbXVsICo9IHBmW2ldOwoJCQl9CgkJaWYgKChvbmVzICYgMSkgPT0gMCkKCQkJcmVzICs9IG0gLyBtdWw7CgkJZWxzZQoJCQlyZXMgLT0gbSAvIG11bDsKCX0KCXJldHVybiByZXM7Cn0KCmludCBtYWluKGludCBhcmdjLCBjaGFyICoqYXJndikgewoJZm9yIChpbnQgcCA9IDA7IHAgPCBOOyArK3ApCgkJc2ZhY1twXSA9IHA7Cglmb3IgKGludCBwID0gMjsgcCAqIHAgPCBOOyArK3ApCgkJaWYgKHNmYWNbcF0gPT0gcCkKCQkJZm9yIChpbnQgcSA9IHAgKiBwOyBxIDwgTjsgcSArPSBwKQoJCQkJc2ZhY1txXSA9IG1pbihzZmFjW3FdLCBwKTsKCWludCBUOwoJc2NhbmYoIiVkIiwgJlQpOwoJd2hpbGUgKFQtLSAhPSAwKSB7CgkJaW50IG07CgkJc2NhbmYoIiVkIiwgJm0pOwoJCWludCBhID0gY29wcmltZXMobSk7CgkJaW50IGIgPSBtIC0gMTsKCQlwcmludGYoIiVsbGRcbiIsIDFMTCAqIGEgKiBiKTsKCX0KCXJldHVybiAwOwp9