// program directly inspired by A247665

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

#define MAX (1LL<<29)	// requires ~ 9Gb

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

int main() {
	sieve = new bool[MAX];
	gpf = new long long[MAX];
	sf = new long long[MAX];
	a = new long long[MAX];

	memset(sieve, 0, MAX*sizeof(*sieve));
	memset(gpf, 0, MAX*sizeof(*gpf));
	memset(sf, 0, MAX*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;
	long long k=0;
	for (long long n=1;; n++) {
		while (sf[v]) {
			v++;
			if (v==MAX) {
				return 0;
			}
		}

		a[n]=v;
		if (gpf[v]!=v) {
			printf("%lld %lld\n", ++k, n);
			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;
}