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

using namespace std;

#define K   4
#define MAX 100000

int sieve[MAX];
bool seen[MAX];
int unseen = 1;

int factorize(int n, map<int,int> &fact) {
	int mx = 0;
	while (n>1) {
		int prime = sieve[n];
		int pow = 0;
		do {
			n /= prime;
			pow++;
		} while (n % prime==0);

		fact[prime] = pow;

		if (mx < pow) {
			mx = pow;
		}
	}
	return mx;
}

int other(int prev) {
	map<int,int> prevfact;
	int mx = factorize(prev, prevfact);
	for (int can=unseen; can<MAX; can++) {
		if (!seen[can]) {
			int remx = mx;
			int rem = can;
			while (rem>1) {
				int prime = sieve[rem];
				int pow = 0;
				if (prevfact.count(prime)) {
					pow = prevfact[prime];
				}
				do {
					rem /= prime;
					pow++;
				} while (rem % prime==0);

				if (remx < pow) {
					remx = pow;
				}
			}

			if (remx>=K) {
				return can;
			}
		}
	}
	fprintf(stderr, "*** the end\n");
	exit(0);
}

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

	int pc = 0;
	for (int n=2; n<MAX; n++) {
		if (!sieve[n]) {
			pc++;
			int m = n;
			while (m<MAX) {
				sieve[m] = n;
				m += n;
			}
		}
	}

	fprintf(stderr, "*** got %d primes up to %d\n", pc, MAX);

	int a;
	for (int n=1; n<=10000; n++) {
		if (n==1) {
			a = 1;
		} else {
			a = other(a);
		}

		printf("%d %d\n", n, a);
		fflush(stdout);
		
		seen[a] = true;
		while (seen[unseen] && unseen < MAX) {
			unseen++;
		}
	}

	return 0;
}