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

#define MAX 15000000

int valuation(int n, int p) {
	int v = 0;
	while (n%p==0) {
		n /= p;
		v++;
	}
	return v;
}

int mask[MAX];	// masks of prime exponents
bool seen[MAX];	// seen ?

void init() {
	memset(mask, 0, sizeof(mask));
	memset(seen, 0, sizeof(seen));
	for (int n=2; n<MAX; n++) {
		if (!mask[n]) {
			// n is prime !
			for (int m=n; m<MAX; m+=n) {
				mask[m] |= 1 << valuation(m,n);
			}
		}
	}
}

int unseen = 1;

int other(int p) {
	seen[p] = true;
	while (seen[unseen] && unseen!=MAX) {
		unseen++;
	}
	for (int v=unseen; v<MAX; v++) {
		if (!seen[v] && (mask[p] & mask[v])==0) {
			return v;
		}
	}
	fprintf(stderr, "the end\n");
	exit(1);
}

int main() {
	init();

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

	return 0;
}