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

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

long long A335791(long long n) {
	long long x1 = 2;
	long long x2 = 2;
	for (;;) {
		x1 = (x1*x1+1) % n;
		x2 = (x2*x2+1) % n;
		x2 = (x2*x2+1) % n;

		long long d = gcd(abs(x1-x2), n);
		if (d>1) {
			return d;
		}
	}
}

#define MAX 60000000LL

bool sieve[MAX];

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

	long long k = 0;
	for (long long n=2; n<MAX; n++) {
		if (sieve[n]) {
			if (A335791(n)==n) {
				printf("%lld %lld\n", ++k, n);
				fflush(stdout);

				if (k==10000LL) {
					break;
				}
			}
		} else {
			for (long long m=n*n; m<MAX; m+=n) {
				sieve[m] = true;
			}
		}
	}

	return 0;
}