#include <iostream>
#include <cstdio>
#include <cstring>
#define ull unsigned long long

using namespace std;

const int MAXN = 10000000;
const int MAXHASH = 1000000;

int T;
ull _n;
int _prime[MAXN];
int _cc;
ull _pphi[MAXN+1] = {0ull, 1ull};
ull _hash[MAXHASH];

void Xxs() {
  for (int i = 2; i <= MAXN; i++) {
    if (!_pphi[i]) {
      _pphi[i] = i-1;
      _prime[_cc] = i;
      _cc++;
    }
    for (int m = 0; m < _cc && _prime[m]*i<=MAXN; m++) {
      if (!(i%_prime[m])) {
	_pphi[_prime[m]*i] = _pphi[i]*_prime[m];
	break;
      }
      _pphi[_prime[m]*i] = _pphi[i]*(_prime[m]-1);
    }
  }
  for (int i = 2; i <= MAXN; i++) {
    _pphi[i]+=_pphi[i-1];
  }
}

inline ull Hash(ull n) {
  return _n/n;
}

ull S(ull n) {
  if (n <= MAXN) return _pphi[n];
  if (_hash[Hash(n)]) return _hash[Hash(n)];
  //cout << n << ',' << endl;
  ull res = n&1?((n+1)>>1)*n:(n>>1)*(n+1);
  for (ull l = 2, r; l <= n; l = r+1) {
    r = n/(n/l);
    res-=(r-l+1)*S(n/l);
  }
  _hash[Hash(n)] = res;
  return res;
}

ull F(ull n) {
  if (n==1) return 0;
  return S(n)+F(n>>1);
}

int main() {
//   freopen("P6860.in", "r", stdin);
  scanf("%d", &T);
  Xxs();
  while (T--) {
    scanf("%llu", &_n);
    memset(_hash, 0, sizeof(_hash));
    printf("%llu\n", F(_n));
  }
//   fclose(stdin);
  return 0;
}