LCM SUM - Euler Totient Function

#include <bits/stdc++.h>
 
#define FOR(i,x,y) for(ll i = (x) ; i <= (y) ; ++i)
 
using namespace std;
typedef long long ll;
 
ll res[1000010];
ll phi[1000010];
 
void precal( int n ) {
    FOR(i,1,n) phi[i] = i;
    FOR(i,2,n) {
        if ( phi[i] == i ) {
        for ( int j = i; j <= n; j += i ) {
            phi[j] /= i;
            phi[j] *= i - 1;
        }
    }
 }
 FOR(i,1,n){
    for ( int j = i; j <= n; j += i ) {
        res[j] += ( i * phi[i] );
    }
 }
}
 
int main () {
    precal( 1000000 );
 
    int t;
    scanf ( "%d",&t );
 
    while ( t-- ) {
        ll n;
        scanf ( "%lld", &n );
        ll ans = res[n] + 1;
        ans *= n;
        ans /= 2;
 
        printf ( "%lld\n", ans );
    }
 
    return 0;
}