#include <bits/stdc++.h>

using namespace std;

int main()
{
    ifstream f("ssnd.in");
    ofstream g("ssnd.out");
    int t,maxx=-1;
    f>>t;
    vector <long> b(t+1,0);
    for (int i=1;i<=t;++i)
    {
        f>>b[i];
        if (b[i]>maxx) maxx=b[i];
    }
    cout<<maxx;
    vector <int> a(maxx+1,0);
    for (long long i=1;i<=maxx;++i)
    {
        a[i]++;
        for (long long j=i+i;j<=maxx;j+=i)
        {
            a[j]++;
        }
    }
    for (long long i=1;i<=t;++i)
    {
        long long x=b[i],s=1+x;
        for (int j=2;j*j<=x;++j)
        {
            if (x%j==0)
            {
                s+=j+x/j;
            }
            if (j*j==x) s-=j;
        }
        g<<a[b[i]]<<" "<<s%9973<<endl;
    }
    return 0;
}