#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 < 10000010 > prim;
int prime[ 100005 ];
int primetot,fact,rasp,cnt,rsp1,rsp2;
long long x;
int n;
int put ( long long a , int b );
void ciur()
{
    for( int i = 2 ; i <= 1e6 + 5 ; i++ )
    {
        if( prim[ i ] == false )
        {
            prime[ ++primetot ] = i;
            for( int j = i + i ; j <= 1e6 + 5 ; j += i )
                prim[ j ] = true;
        }
    }
}
void descompune( long long x )
{
    rsp1 = 1;
    rsp2 = 1;
    int a = 1;
    int b = 1;
    for( int i = 1 ; x / prime[ i ] >= prime[ i ] ; i++ )
    {
        if( x % prime[ i ] == 0 )
        {
            cnt = 0;
            while( x % prime[ i ] == 0 )
            {
                x /= prime[ i ];
                cnt++;
            }
            a = ( a * ( put( prime[ i ] , cnt + 1 ) - 1 ) ) % mod;
            b = ( b * ( prime[ i ] - 1 ) ) %  mod ;
            rsp1 = ( rsp1 * ( cnt + 1 ) ) % mod;
        }
    }
    if( x != 1 )
    {
        a = ( a * ( put( x , 2 ) - 1 ) ) % mod;
        b = ( b * ( x - 1 ) ) % mod;
        rsp1 = ( rsp1 * 2 ) % mod;
    }
    fout<<rsp1<<" "<<( a * put( b , mod - 2 ) ) % mod<<'\n';
    ///fout<<a<<" "<<b<<'\n';
}
int main()
{
    ciur();
    fin>>n;
    for( int i = 1 ; i <= n ; i++ )
    {
        fin>>x;
        descompune( x );
    }
}
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;
}