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

#define MAX 1000000

bool sieve[MAX];

int avoid(int n, int i) {
	if (n==0) {
		return i;
	} else if (n%2) {
		return 2*avoid(n/2,i);
	} else {
		return 2*avoid(n/2,i/2) + (i%2);
	}
}

int compute(int n) {
	for (int i=0;; i++) {
		int k = n + avoid(n,i);
		if (k>=MAX) {
			fprintf(stderr, "*** the end\n");
			fflush(stderr);
			exit(1);
		}

		if (!sieve[k]) {
			sieve[k] = true;
			return k;
		}
	}
}

int main() {
	memset(sieve, 0, sizeof(sieve));
	sieve[0] = true;
	sieve[1] = true;
	int pc = 0;
	for (int n=2; n<MAX; n++) {
		if (!sieve[n]) {
			pc++;
			int m = 2*n;
			while (m<MAX) {
				sieve[m] = true;
				m += n;
			}
		}
	}
	fprintf(stderr, "*** got %d primes up to %d\n", pc, MAX);
	fflush(stderr);

	for (int n=1; n<=10000; n++) {
		printf("%d %d\n", n, compute(n));
		fflush(stdout);
	}

	return 0;
}