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

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

#define MAX 15000000
int rad[MAX];	// A007947, 0 means already used
bool isprime[MAX];
int unseen = 1;

#define K 3
int rrr[K];

int other() {
	int forbidden = rrr[0];
	for (int k=1; k<K; k++) {
		forbidden = gcd(forbidden, rrr[k]);
	}
	int mandatory = rrr[K-1] / gcd(forbidden, rrr[K-1]);

	for (int v=mandatory*(unseen/mandatory); v<MAX; v+=mandatory) {
		if (rad[v] && gcd(forbidden, v)==1) {
			for (int k=1; k<K; k++) {
				rrr[k-1] = rrr[k];
			}
			rrr[K-1] = rad[v];
			rad[v] = 0;	// using v

			while (unseen<MAX && rad[unseen]==0) {
				unseen++;
			}

			return v;
		}
	}

	exit(0);
}

int main() {
	memset(isprime, 0, sizeof(isprime));
	for (int n=1; n<MAX; n++) {
		rad[n] = 1;
	}
	for (int n=2; n<MAX; n++) {
		if (rad[n]==1) {
			// n is prime
			isprime[n] = true;
			for (int m=n; m<MAX; m+=n) {
				rad[m] *= n;
			}
		}
	}
	rad[0] = 0;	// avoid 0

	for (int n=0; n<K; n++) {
		rrr[n] = 1;
	}

	int ppp = 1;
	int pp = 1;
	int k = 0;
	for (int n=1;; n++) {
		int v = other();

		if (isprime[v] && ppp%v==0 && pp%v==0) {
			printf("%d %d\n", ++k, n);
			fflush(stdout);
			if (k==10000) {
				break;
			}
		}

		ppp = pp;
		pp = v;
	}

	return 0;
}