#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 2000000000ll

bool *sieve = 0;
unsigned char *xdiv = 0;

long long seen[256];
int unseen = 0;

int main() {
	sieve = (bool*)malloc(MAX*sizeof(*sieve));
	xdiv = (unsigned char*)malloc(MAX*sizeof(*xdiv));
	if (sieve==0 || xdiv==0) {
		fprintf(stderr, "# out of memory");
		exit(1);
	}

	memset(sieve, 0, MAX*sizeof(*sieve));
	memset(xdiv, 0, MAX*sizeof(*xdiv));
	memset(seen, 0, sizeof(seen));

	sieve[1] = true;

	long long pi = 0;
	for (long long n=1; n<MAX; n++) {
		if (!sieve[n]) {
			pi++;
			for (long long m=n; m<MAX; m+=n) {
				sieve[m] = true;
				if (m%pi==0) {
					xdiv[m]++;
				}
			}
		}
		if (!seen[xdiv[n]]) {
			seen[xdiv[n]] = n;
			while (seen[unseen]) {
				printf("%d %lld\n", unseen, seen[unseen]);
				fflush(stdout);
				unseen++;
			}
		}
	}

	return 0;
}