Untitled

#include <bits/stdc++.h>

#define int long long
#define ll long long
#define II pair<int, int>
#define fs first
#define sc second
#define endl '\n'

#define mp(x, y) make_pair(x, y)
#define sz(x) ((int) (x.size()))
#define forlr(i, l, r) for(int i = l; i <= r; ++i)
#define forrl(i, r, l) for(int i = r; i >= l; --i)
#define show(v) for(auto i : v) cout << i << " "; cout << endl;
#define showlr(v, l, r) for (int i = l; i <= r; i++) cout << v[i] << " "; cout << endl;
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end());

const long long LINF = 1ll << 60;
const int INF = 1 << 30;
const int N = 1e6 + 5;

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 

bool last_subtask;
int q, n = 1000000;
int a[N];

int cnt[N];

void Sub123() {
    forlr(i, 1, n) {
        for(int j = i; j <= n; j += i) cnt[j] += i;
    }

    forlr(i, 1, q) cout << cnt[a[i]] << " ";
    cout << endl;
}

bool nonPrime[N];
vector<II> fac[N];

void Sub4() {
    int L = a[1], R = a[q];

    nonPrime[2] = false;
    for(int i = 4; i <= n; i += 2) nonPrime[i] = true; 
    for(int i = 3; i <= n; i += 2) {
        if(!nonPrime[i]) {
            for(int j = i * i; j <= n; j += i) {
                nonPrime[j] = true;
            }
        }
    }

    forlr(prime, 2, 2) {
        if(nonPrime[prime]) continue;
        for(int j = ((L + prime - 1) / prime) * prime; j <= R; j += prime) {
            int x = j, cp = 0;
            while(x % prime == 0) x /= prime, cp++;
            fac[j - L + 1].push_back({prime, cp});
        }
    }

    forlr(i, 1, q) {
        if(fac[i].empty()) fac[i].push_back({a[i], 1});

        cout << a[i] << ": " << endl;
        for(II v : fac[i]) {
            cout << " + " << v.fs << " " << v.sc << endl;
        }
        cout << endl;
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    freopen("S.INP", "r", stdin);
    freopen("S.OUT", "w", stdout);

    cin >> q;

    last_subtask = true;
    forlr(i, 1, q) {
        cin >> a[i];

        if(i > 1 && a[i] != a[i - 1] + 1) last_subtask = false;
    }

    if(!last_subtask) Sub123();
    else Sub4();

    return 0;
}