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

#define MAX     5000000
#define WANTED    10000
#define DIST          3

int lpf[MAX];
int a[WANTED];

bool toclose(int m, int n) {
	int d = 0;
	while (m>1 || n>1) {
		int p = lpf[(m>1) ? m : n];
		int v = 0;
		while (m%p==0) {
			v++;
			m/=p;
		}
		while (n%p==0) {
			v--;
			n/=p;
		}
		if (v>0) {
			d+=v;
		} else if (v<0) {
			d-=v;
		}

		if (d>=DIST) {
			break;
		}
	}
	return d<DIST;
}

int main() {
	memset(lpf, 0, sizeof(lpf));
	for (int n=2; n<MAX; n++) {
		if (lpf[n]==0) {
			for (int m=n; m<MAX; m+=n) {
				if (lpf[m]==0) {
					lpf[m] = n;
				}
			}
		}
	}

	int n = -1;

	for (int v=1; v<MAX; v++) {
		bool ok = true;

		for (int k=0; k<=n; k++) {
			if (toclose(a[k], v)) {
				ok = false;
				break;
			}
		}

		if (ok) {
			n++;
			a[n] = v;
			printf ("%d %d\n", n+1, a[n]);
			fflush(stdout);

			if (n+1==WANTED) {
				break;
			}
		}
	}

	return 0;
}