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

constexpr int MOD = 9973;
bitset<1000001> isPrime;
vector<int> prime;

void erathostenes()
{
    for(int i = 0; i <= 1000000; ++i)
        isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;
    
    for(int i = 2; i * i <= 1000000; ++i)
        if(isPrime[i])
            for(int j = i * i; j <= 1000000; j += i)
                isPrime[j] = false;
    
    for(int i = 2; i <= 1000000; ++i)
        if(isPrime[i])
            prime.push_back(i);
}

int lgput(int a, int n, int MOD)
{
    int p = 1;
    a %= MOD;
    for(; n; n >>= 1) {
        if(n & 1)
            p = p * a % MOD;
        a = a * a % MOD;
    }
    return p % MOD;
}

int invMod(int x)
{
    return lgput(x, MOD-2, MOD);
}

void solve()
{
    int n;
    cin >> n;
    
    long long sum = 1, prod = 1;
    
    for(int i = 0; 1LL * prime[i] * prime[i] <= n; ++i) {
        int p = 0;
        while(n % prime[i] == 0) {
            n /= prime[i];
            ++p;
        }
        if(p) {
            sum *= p + 1;
            prod *= (((lgput(prime[i], p + 1, MOD)) - 1) * invMod(prime[i] - 1)) % MOD;
        }
    }
}

signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    // freopen("ssnd.in", "r", stdin);
    // freopen("ssnd.out", "w", stdout);
    
    erathostenes();
    
    int t;
    cin >> t;
    while(t--)
        solve();
}