#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
typedef int Int;
typedef long long lInt;
constexpr Int MAXN = 1000000;
Int N, T, phi[1 + MAXN], low[1 + MAXN];
lInt ans[1 + MAXN];
std:: vector<Int> prime;
void init(){
    phi[1] = 1;
    for (Int i = 2 ; i <= MAXN ; i++){
        if (low[i] == 0){
            low[i] = i;
            phi[i] = i - 1;
            prime.emplace_back(i);
        }
        for (Int p: prime){
            if (p > low[i] || p * i > MAXN) break;
            low[p * i] = p;
            if (p != low[i]){
                phi[i * p] = phi[p] * phi[i];
            } else {
                phi[i * p] = p * phi[i];
            }
        }
    }
}
void work(){
    if (ans[N] != 0){
        std:: cout << ans[N] << '\n';
        return ;
    }
    lInt res = 1;
    for (lInt i = 1 ; i * i <= N ; i++){
        if (N % i == 0){
            res += (i * phi[i]) >> 1;
            if (i * i != N) res += (N / i * phi[N / i]) >> 1;
        }
    }
    std:: cout << (ans[N] = N * res) << '\n';
}
int main(){
    std:: ios:: sync_with_stdio(false);
    std:: cin.tie(nullptr);
    std:: cin >> T;
    init();
    for (Int i = 1 ; i <= T ; i++){
        std:: cin >> N;
        work();
    }
    return 0;
}

最小的数据跑了20ms,应该不会是线性筛的问题吧...