#include <iostream>
#include <fstream>
#include <math.h>
#include <chrono>
using namespace std;

#define LL long long
#define MOD 9973

ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
int nrdiv;
LL sdivfinal;

void solve(LL x) {
    LL d = 2;
    nrdiv = 1;
    LL sdiv1 = 1, sdiv2 = 1;

    // scot factorii primi lui x
    while (x > 1) {
        int e = 0;
        while (x % d == 0) {
            e++;
            x /= d;
        }
        if (e) {
            nrdiv *= e + 1;
            sdiv1 *= (LL)pow(d, e+1) - 1;
            sdiv2 *= d - 1;
        }
        d++;
    }
    sdivfinal = (sdiv1 / sdiv2) % MOD;
}

int main() {
    int t;
    fin >> t;

    auto start = chrono::high_resolution_clock::now();

    LL x;
    for (int i = 0; i < t; i++) {
        fin >> x;
        cout << x << ": ";
        solve(x);
        cout << nrdiv << " " << sdivfinal << endl;
        fout << nrdiv << " " << sdivfinal << endl;
    }

    auto stop = chrono::high_resolution_clock::now();
    auto timp = chrono::duration_cast<chrono::microseconds>(stop - start);
    cout << endl << endl << (double)timp.count() / 1000.0 << " ms";

    return 0;
}