#include <stdio.h>
#include <math.h>

int main()
{
    FILE *fin = fopen("ssnd.in", "r");
    FILE *fout = fopen("ssnd.out", "w");

    int n, m, s, nd;
    float f;
    fscanf(fin, "%d", &n);

    int MAX = 1000000;
    int *ciur, *vect;
    ciur = malloc(MAX * sizeof(int));
    memset(ciur, 0, MAX * sizeof(int));
    vect = malloc(MAX * sizeof(int));
    int i, j, k;
    for(i =  2; i < n; i++)
        if(ciur[i] == 0)
            for(j = i + i; j < MAX; j+=i)
                ciur[j] = 1;

    for(i = 0; i < n; i++)
    {
        fscanf(fin, "%d", &m);
        s = 1 + m;
        nd = 2;
        f = sqrt(m);
        memset(vect, 0, m/2 * sizeof(int));
        for(j = 2; j <= f; j++)
        {
            if(ciur[j] == 0)
            {
                if(m % j == 0)
                {
                    s += j;
                    nd ++;
                    for(k = j + j; k <= m/2; k+=j)
                    {
                        if((m % k) == 0 && vect[k] == 0)
                        {
                            vect[k] = 1;
                            s += k;
                            nd++;
                        }
                    }
                }
            }
        }
        fprintf(fout, "%d %d\n", nd, s % 9973);
    }
    return 0;
}