#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <climits>
#define MOD 9973

using namespace std;

FILE * f = fopen("ssnd.in", "r");
FILE * g = fopen("ssnd.out", "w");

bool isColorat[4000001];

int main()
{
    long long n;
    int x, suma, s;
    fscanf(f, "%lld", &n);
    for (long long i = 2; i <= 4000000; i++)
    {
        if (isColorat[i] == 0)
        {
            for (long long j = 2 * i; j <= 4000000; j = j + i)
                isColorat[j] = 1;
        }
    }
    for (long long i = 1; i <= n; i++)
    {
        fscanf(f, "%i", &x);
        if (isColorat[x] == 0)
        {
            suma = (1 + x % MOD) % MOD;
            fprintf(g, "%i %i\n", 2, suma);
        }
        else
        {
            suma = 1;
            s = 1;
            for (int d = 2; d <= x; d++)
            {
                if (x % d == 0)
                {
                    s++;
                    suma = (suma + d % MOD) % MOD;
                }
            }
            suma = suma % MOD;
            fprintf(g, "%i %i\n", s, suma);
        }
    }
    return 0;
}