Author: skyvn97

Xem: https://www.youtube.com/live/qWz664WCmJw?si=mX9ZCtS6Ry5dFNqq

#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define fi   first
#define se   second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }

/* Author: Van Hanh Pham */

/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/

#define MAX   20002000
#define SQRT   4545
#define LENGTH   25
const int MOD = (int)1e9 + 22071997;

int result[MAX + 3], pw[SQRT + 3][LENGTH + 3];
bool coprime[SQRT + 3][SQRT + 3];
int primeDiv[MAX + 3];
long long savedResult[MAX + 3];

int getPw(int x, int k) {
    if (k == 0) return 1;
    if (k == 1) return x;
    return x > SQRT ? MAX + 1 : pw[x][k];
}

int getSum(int p, int q, int k) {
    long long res = 0;
    REP(i, k + 1) {
        res += 1LL * getPw(p, i) * getPw(q, k - i);
        if (res > MAX) return MAX;
    }
    return res;
}

void prepare(void) {
    REP(i, 2) primeDiv[i] = -1;
    for (int i = 2; i * i <= MAX; i++) if (primeDiv[i] == 0)
        for (int j = i * i; j <= MAX; j += i) primeDiv[j] = i;
    FOR(i, 2, MAX) if (primeDiv[i] == 0) primeDiv[i] = i;

    FOR(i, 1, SQRT) FOR(j, 1, SQRT) coprime[i][j] = true;
    FOR(i, 2, SQRT) if (primeDiv[i] == i)
        for (int j = i; j <= SQRT; j += i) for (int k = i; k <= SQRT; k += i) coprime[j][k] = false;

    FOR(i, 1, SQRT) {
        pw[i][0] = 1;
        FOR(j, 1, LENGTH) pw[i][j] = min(1LL * MAX, 1LL * pw[i][j - 1] * i);
    }

    FOR(k, 2, LENGTH) FOR(q, 1, SQRT) {
        if (pw[q][k] >= MAX) break;
        FOR(p, q + 1, SQRT) {
            int sum = getSum(p, q, k);

            if (sum >= MAX) break;
            if (!coprime[p][q]) continue;
            result[sum]++;
        }
    }
}

vector<pair<int, int>> factors;
void backtrack(int pos, int val, long long &sum) {
    if ((int)pos >= factors.size()) {
        sum += result[val];
        return;
    }

    int tmp = val, pr = factors[pos].fi;
    FOR(i, 0, factors[pos].se) {
        backtrack(pos + 1, tmp, sum);
        if (i < factors[pos].se) tmp *= pr;
    }
}

int solve(int n) {
    if (n < 3) return 0;

    long long &res = savedResult[n];
    if (res > 0) return res;

    res = n % 2 == 0 ? n / 2 - 1 : n / 2;

    factors.clear();
    while (n > 1) {
        int p = primeDiv[n];
        factors.push_back(make_pair(p, 0));
        while (n % p == 0) {
            factors.back().se++;
            n /= p;
        }
    }

    backtrack(0, 1, res);

    return res % MOD;
}

int main(void) {
#ifdef ONLINE_JUDGE
    freopen("geometric.inp", "r", stdin);
    freopen("geometric.out", "w", stdout);
#endif // ONLINE_JUDGE

    prepare();

    int input; scanf("%d", &input);
    while (scanf("%d", &input) == 1) printf("%d ", solve(input)); printf("\n");
    return 0;
}

/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/