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

int pNum[10000];

bool checkPrime(int x){
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}

void findFactor(int x){
	for(int i=x;i>1;i--){
		for(int j=2;j<=x;j++){
			if(checkPrime(j) && i%j==0){
				int temp = i;
				while(temp%j==0){
					pNum[j]++;
					temp/=j;
				}
			}
		}
	}
}

int main(){
	int tc;
	scanf("%d",&tc);
	for(int i=1;i<=tc;i++){
		int in, now = 0,count=0;
		scanf("%in",&in);
		printf("Case #%d:\n",i);
		findFactor(in);
		for(int j=2;j<=10000;j++){
			if(pNum[j]!=0){
				printf("%d %d\n",j,pNum[j]);
				count-=pNum[j];
			}
			pNum[j] = 0;
			if(j>in){
				break;
			}
		}
	}
	return 0;
}