#include <fstream>
#include <bitset>
#define x first
#define y second
using namespace std;
ofstream fout ("ssnd.out");
ifstream fin ("ssnd.in");
const int mod = 9973;
bitset < 1000005 > prim;
long long prime[ 100005 ];
long long primetot,fact,rasp,cnt;
pair < long long , int > factori[ 100005 ];
long long x;
int n;
int put ( long long a , int b );
void ciur()
{
    for( int i = 2 ; i <= 1e6 ; i++ )
    {
        if( prim[ i ] == false )
        {
            prime[ ++primetot ] = i;
            for( int j = i + i ; j <= 1e6 ; j += i )
                prim[ j ] = true;
        }
    }
}
void descompune( int x )
{
    fact = 0;
    for( int i = 1 ; i <= primetot ; i++ )
    {
        if( x % prime[ i ] == 0 )
        {
            cnt = 0;
            while( x % prime[ i ] == 0 )
            {
                x /= prime[ i ];
                cnt++;
            }
            factori[ ++fact ] = make_pair( prime[ i ] , cnt );
        }
    }
    if( x != 1 )
    {
        factori[ ++fact ] = make_pair( x , 1 );
    }
}
void calc_si_afis()
{
    rasp = 1;
    for( int i = 1 ; i <= fact ; i++ )
        rasp = rasp * ( factori[ i ].y + 1 ) % mod;
    fout<<rasp<<" ";
    rasp = 1;
    long long a = 1;
    long long b = 1;
    for( int i = 1 ; i <= fact ; i++ )
    {
        int aux = 1;
        aux = put( factori[ i ].x , factori[ i ].y + 1 );
        aux--;
        a = ( a * aux ) % mod;
        b = ( b * ( ( factori[ i ].x - 1 ) % mod ) % mod );
    }
    rasp = ( ( a % mod ) * put( b , mod - 2 ) ) % mod;
    fout<<rasp<<'\n';
}
int main()
{
    ciur();
    fin>>n;
    for( int i = 1 ; i <= n ; i++ )
    {
        fin>>x;
        descompune( x );
        calc_si_afis();
    }
}
int put ( long long a , int b )
{
    int rsp = 1;
    for( int i = 0 ; ( 1 << i ) <= b ; i++ )
    {
        if( ( 1 << i ) & b )
            rsp = ( rsp * a ) % mod;
        a = ( a * a ) % mod;
    }
    return rsp;
}