#include <cstdio>
#include <bitset>
#include <vector>

using namespace std;

FILE * iFile;
FILE * oFile;

bitset<1500000> nums;
int t;
long n;

void mark()
{
	long i, j;
	
	for(i=2;i<=1000000;i++)
	{
		if(nums[i] == 0)
		{
			for(j=i+i;j<=1000000;j=j+2*i)
			{
				nums[j] = 1;
				nums[j+i] = 1;
			}
		}
	}
}

void read()
{
	fscanf(iFile, "%d", &t);
}
int main()
{
	iFile = fopen("ssdn.in", "r");
	oFile = fopen("ssdn.out", "w");
	
	long s, count, i, j;
	
	read();
	mark();
	
	s = 0;
	count = 0;
	
	for(i=1;i<=t;i++)
	{
		fscanf(iFile, "%ld", &n);	
		
		s = n + 1;
		count = 2;
		
		if(nums[n] == 1)		
		{			
			for(j=2;j<=n/2;j++)
			{
				if(n % j == 0)
				{					
					s = (s  + j) %  9973;
					count++;
				}
			}
		}
		
		fprintf(oFile, "%ld ", count);
		fprintf(oFile, "%ld\n", s);
		
		s = 0;
		count = 0;
		
	}
		
	fclose(iFile);
	fclose(oFile);
	
	return 0;
}