NT-problem-J

#include <bits/stdc++.h>
using namespace std;

#define MAXN        500000

std::vector <int> prime;
bool is_composite[MAXN];

void sieve (int n) {
    std::fill (is_composite, is_composite + n, false);
    for (int i = 2; i < n; ++i) {
        if (!is_composite[i]) prime.push_back (i);
        for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) {
            is_composite[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

long long SOPD(ll x)
{
    ll sod = 1, p;

    while(true) {
        for(auto y : prime) {
            if(y > x) break;
            if((x % y) == 0) {
                p = y;
                while((x % y) == 0) {
                    x /= y;
                    p *= y;
                }
                sod *= (p - 1) / (y - 1);
            }
        }
        if(x == 1) break;
    }
    return (sod);
}


int main()
{
    int t;
    cin >> t;
    ll n, sopd;

    sieve(MAXN);

    while(t--) {
        cin >> n;
        sopd = SOPD(n);
        cout << sopd - n << endl;
    }


    r0;
}

//ALHAMDULILLAH