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

#define MAX 100000

int *tab = 0;
int pc = 0;
int *first = 0;

int lastpi = 0;
int unseen = 1;

int other(int v) {
	first[lastpi] = tab[v];
	tab[v] = 0;
	while (unseen < MAX && tab[unseen]==0) {
		unseen++;
	}

	int best = MAX;
	int bestpi = 0;
	for (int pi=1; pi <= lastpi+1 && pi <= pc; pi++) {
		if (first[pi] < best) {
			best = first[pi];
			bestpi = pi;
		}
	}

	if (best<MAX) {
		lastpi = bestpi;
		return best;
	} else {
		fprintf(stderr, "the end\n");
		exit(0);
	}
}

int main() {
	tab = (int*) malloc(MAX * sizeof(int));
	if (tab==0) {
		fprintf(stderr, "out of memory\n");
		exit(1);
	}

	memset(tab, 0, MAX * sizeof(int));
	for (int n=2; n<MAX; n++) {
		if (!tab[n]) {
			pc++;
			for (int m=n; m<MAX; m+=n) {
				tab[m] = 1;
			}
		}
	}
	fprintf(stderr, "got %d primes up to %d\n", pc, MAX);

	first = (int*) malloc((1+pc) * sizeof(int));
	if (first==0) {
		fprintf(stderr, "out of memory\n");
		exit(1);
	}

	memset(tab, 0, MAX * sizeof(int));
	memset(first, 0, (1+pc) * sizeof(int));

	int pi = 0;
	for (int n=2; n<MAX; n++) {
		if (!tab[n]) {
			pi++;
			first[pi] = n;

			int p = n;
			for (int m=2*n; m<MAX; m+=n) {
				if (!tab[m]) {
					tab[p] = m;
					p = m;
				}
			}
			tab[p] = MAX;
		}
	}

	int v = 1;
	for (int n=1; n<=10000; n++) {
		printf("%d %d\n", n, v);
		fflush(stdout);
		v = other(v);
	}

	free(tab);

	return 0;
}