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

long long gcd(long long a, long long b) {
	while (a != 0) {
		long long c = a;
		a = b%a;
		b = c;
	}
	return (b<0) ? -b : +b;
}

#define MAX 1000000
bool seen[MAX];
long long unseen = 1;
long long unseenOdd = 1;

#define WANTED 10001
long long a[WANTED];
long long u = 1;

int main() {
	memset(seen, 0, sizeof(seen));
	memset(a, 0, sizeof(a));

	long long ppp = 1;
	long long pp = 1;
	long long p = 1;

	for (long long n=1; u<WANTED; n++) {
		bool found = false;
		long long x = ppp*pp*p;
		long long v;
		long long step;

		if (x%2==0) {
			v = unseenOdd;
			step = 2;
		} else {
			v = unseen;
			step = 1;
		}

		for (; v<MAX; v+=step) {
			if (!seen[v] && gcd(v, x)==1) {
				found = true;
				break;
			}
		}

		if (found) {
			if (v<WANTED) {
				a[v] = n;
				while (u < WANTED && a[u]) {
					printf("%lld %lld\n", u, a[u]);
					fflush(stdout);

					u++;
				}
			}


			seen[v] = true;
			while (unseen < MAX && seen[unseen]) {
				unseen++;
			}
			while (unseenOdd < MAX && seen[unseenOdd]) {
				unseenOdd+=2;
			}

			ppp = pp;
			pp = p;
			p = v;
		} else {
			break;
		}
	}

	return 0;
}