#include<stdio.h>
#include<unistd.h>
#include<math.h>
#include<string.h>
#define M 1000000
#define q 9973
char vect[M];

void eratostene() {
	int cur_pos = 2;
	int i;

	while( cur_pos <= M) {
		for( i = cur_pos*2; i<= M; i+=cur_pos){
			vect[i] = 0;
		}
		cur_pos++;
		while(vect[cur_pos] == 0 && cur_pos <= M) {
			cur_pos++;
		}
	}	
}

void sol(int num, FILE* file){
	int i, count, sum;
	int max_pow_c;// return the max pow from the prime num decomposition
	int  max_pow_r;//ret the mux num from the prime num decomposition
	count = 1;
	sum = 1 ;
	for(i = 2; i <= num/2; i++) {
		if ((vect[i] == 1) && (num % i == 0)){
			max_pow_c = 1;
			max_pow_r = i;
			while(num % max_pow_r == 0) {
				max_pow_c++;
				max_pow_r = (max_pow_r*i);
			}
			
			count*=max_pow_c;
			sum = (sum * (((max_pow_r - 1)/(i - 1))%q))%q;
			
		}
	}
	//prime numbers
	if(count==1 && sum ==1) {
		count+=1;
		sum = (sum + (num%q) )%q;
	}
	//write the count and sum to file
	fprintf(file, "%d %d\n", count, sum);	
}

int main(){
	int t, num, i;
	FILE* fin = fopen("ssnd.in", "r");
	FILE* fout = fopen("ssnd.out", "w");
	memset(vect, 1, M*sizeof(char));
	eratostene();
	printf("eratostene reslt\n");
	for(i = 0; i < 13; i++) {
		printf(" %d", (int) vect[i]);
	}
	
	fscanf(fin, "%d\n", &t);
	for(i = 0; i < t; i++){
		fscanf(fin, "%d\n", &num);
		sol(num, fout);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}