#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
//#include <conio.h>

int main() {
    
    int max = 1000000;
    int mod = 9973;
    int ok,cate =2;
    
    FILE *f = fopen("ssnd.in","rt"), *g = fopen("ssnd.out","wt");
    int j,i,t,n,k = 1;
    
    int p[1006]; p[0] = 1;
    int viz[1006] = {0} ;
    for (i = 2; i <= max; i++){
        if (viz[i] == 0)
         {
                   viz[i] = 1; 
                   p[k] = i; k++;
                   for (j = i+i; j <= max; j+= i){
                       viz[j] = 1;
                   }
         }
    }
    int nn;
    fscanf(f,"%i",&t);
    int sum = 1,put;
    k = 1; int poo =1;
    //for (i =0; i< 10; i++) fprintf(g,"%i ",p[i]);
    for (i = 1; i <= t; i++){
        fscanf(f,"%i",&n);
        nn = n;
        sum = (1+n) % mod;
        k = 1;cate = 2; poo = 1;
        while ( p[k] <=(int)sqrt(n)) {
              
              if (n % p[k] == 0){
                    
                    if (p[k] != n/p[k] ) {sum = (sum + p[k] + n/p[k]) % mod; cate++; cate++;}
                              else if (poo == 1){ sum = (sum + p[k]) % mod; cate++; poo = 0;}
                   ok = 1;
                   put = p[k] + p[k-1] * p[k];
                   //n = n / p[k];
                   while (ok)
                   {
                         if (n % put == 0 )
                         {//n = n  / p[k];
                         if (put > (int)sqrt(n) ) {ok = 0; }
                         else{
                              if (put != n/put ) {sum = (sum + put + n/put) % mod; cate++; cate++;}
                              else if (poo == 1){ sum = (sum + put) % mod; cate++; poo = 0;}
                         
                         put = put + p[k-1] *p[k]; 
                         
                         }
                               }
                         else put = put + p[k];
                   }     
                   k++;
              }
              else k++; 
        }
        //sum = (sum + n) % mod;
        fprintf(g,"%i %i\n",cate,sum);
    }
    
     
    fclose(f);
    fclose(g);
    
    
    
    
    
    
    return 0;
}