// program directly inspired by A247665

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

#define MAX 105000

bool 		sieve[MAX];	// prime sieve
long long	gpf  [MAX];	// greatest prime factor
long long	sf   [MAX];	// selection sieve (0 = available)
long long	a    [MAX];	// A354790

int main() {
	memset(sieve, 0, sizeof(sieve));
	memset(gpf, 0, sizeof(gpf));
	memset(sf, 0, sizeof(sf));

	for (long long n=2; n<MAX; n++) {
		if (!sieve[n]) {
			for (long long m=n; m<MAX; m+=n) {
				sieve[m] = true;
				gpf[m] = n;
			}
			// mark non-squarefree numbers
			long long n2 = n*n;
			for (long long s=n2; s<MAX; s+=n2) {
				sf[s]++;
			}
		}
	}

	long long v=1;
	for (long long n=1;; n++) {
		while (sf[v]) {
			v++;
			if (v==MAX) {
				return 0;
			}
		}

		printf("%lld %lld\n", n, a[n]=v);
		fflush(stdout);

		sf[v]++;

		// mark out numbers not coprime to v
		long long r=v;
		while (r>1) {
			long long g=gpf[r];
			r/=g;

			for (long long m=g; m<MAX; m+=g) {
				sf[m]++;
			}
		}

		if (n%2==0) {
			long long r=a[n/2];
			while (r>1) {
				long long g=gpf[r];
				r/=g;

				for (long long m=g; m<MAX; m+=g) {
					sf[m]--;
					if (sf[m]==0 && v>m) {
						v=m;
					}
				}
			}
		}
	}

	return 0;
}