#include <cstdio>
#include <cstdlib>

using namespace std ;

const int MODULO = 9973 ;
const int PINV = 9971 ;

bool ciur [ 1000000 ] ;

void generareCiur ( ) ;

inline int ridicarePutere ( int Baza , int Exponent )
{
  int bit = 1 , rezultat = 1 ;
  while ( Exponent )
  {
    if ( Exponent & bit )
    {
      rezultat *= Baza ;
      rezultat %= MODULO ;
    }
    Exponent >>= 1 ;
    Baza *= Baza ; 
    Baza %= MODULO ;
  }
  return rezultat ;
}

int main ( )
{
  freopen ( "ssnd.in" , "r" , stdin ) ;
  freopen ( "ssnd.out" , "w" , stdout ) ;
  int sumaCurenta , nrTermeni , nrDivizori , p ;
  long long termenCurent ;
  scanf ( "%d" , &nrTermeni ) ;
  generareCiur ( ) ;
  for ( int i = 0 ; i < nrTermeni ; ++i )
  {
    scanf ( "%lld" , &termenCurent ) ;
    sumaCurenta = 1 ;
    nrDivizori = 1 ;
    for ( int j = 2 ; j <= 2 ; ++j )
    {
      if ( termenCurent == 1 )
	break ;
      if ( ciur [ j ] )
	continue ;
      p = 1 ;
      while ( termenCurent % j == 0 )
      {
	termenCurent /= j ;
	++p ;
      }
      if ( p > 1 )
      {
	sumaCurenta *= ( ridicarePutere ( j , p ) - 1 ) ;
	sumaCurenta %= MODULO ;
	sumaCurenta *= ridicarePutere ( j - 1 , PINV ) ;
	sumaCurenta %= MODULO ;
	nrDivizori *= p ;
      }
    }
    for ( int j = 3 ; j < 1000000 ; j+=2 )
    {
      if ( termenCurent == 1 )
	break ;
      if ( ciur [ j ] )
	continue ;
      p = 1 ;
      while ( termenCurent % j == 0 )
      {
	termenCurent /= j ;
	++p ;
      }
      if ( p > 1 )
      {
	sumaCurenta *= ( ridicarePutere ( j , p ) - 1 ) ;
	sumaCurenta %= MODULO ;
	sumaCurenta *= ridicarePutere ( j - 1 , PINV ) ;
	sumaCurenta %= MODULO ;
	nrDivizori *= p ;
      }
    }
    if ( termenCurent > 1 )
    {
      termenCurent += sumaCurenta ;
      termenCurent %= MODULO ;
      printf ( "%d %lld\n" , nrDivizori << 1 , termenCurent ) ;
    }
    else
      printf ( "%d %d\n" , nrDivizori , sumaCurenta ) ;
  }
}

void generareCiur ( )
{
  for ( int i = 4 ; i <= 1000000 ; i += 2 )
    ciur [ i ] = true ;
  for ( int i = 3 ; i < 1000000 ; i+=2 )
  {
    if ( ciur [ i ] )
      continue ;
    for ( int j = 2 * i ; j < 1000000 ; j += i )
    {
      ciur [ j ] = true ;
    }
  }
}