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

#define MAX 1000000000

bool *sieve = 0;
int *nb = 0;

int main() {
	sieve = (bool*)malloc(MAX * sizeof(bool));
	memset(sieve, 0, MAX * sizeof(bool));

	nb = (int*)malloc(MAX * sizeof(int));
	memset(nb, 0, MAX * sizeof(int));

	int u = 1;
	for (int n=2; n<MAX; n++) {
		if (!sieve[n]) {
			// prime
			for (int m=n; m<MAX; m+=n) {
				sieve[m] = true;
			}
		} else {
			// non prime
			for (int m=n; m<MAX; m+=n) {
				nb[m]++;
			}
		}

		int v = 1;
		for (int m=n-1; m>0 && nb[m]==nb[m+1]; m--) {
			v++;
		}
		while (u<=v) {
			printf("%d %d\n", u, n-v+1);
			u++;
			fflush(stdout);
		}
	}

	return 0;
}