#include <bitset>
#include <iostream>
#include <map>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define MAXPRIME	17179869184ll
bitset<MAXPRIME> *sieve = 0;

#define BIGMIN	1000000
bool smallseen[BIGMIN];
map<long long,bool> bigseen;

void see(long long v) {
	if (v<BIGMIN) {
		smallseen[v] = true;
	} else {
		bigseen[v] = true;
	}
}

bool seen(long long v) {
	if (v<BIGMIN) {
		return smallseen[v];
	} else {
		return bigseen.count(v)>0;
	}
}

long long sumdigits(long long n) {
	long long s = 0;
	while (n) {
		s += n % 10;
		n /= 10;
	}
	return s;
}

long long sum = 0;
long long dsum = 0;

long long other() {
	for (long long v=1;; v++) {
		if (!seen(v)) {
			long long sumv = sum + v;
			if (sumv>=MAXPRIME) {
				cerr << "# the end" << endl;
				exit(0);
			}
			if (!sieve->test(sumv)) {
				long long dsumv = dsum + sumdigits(v);
				if (!sieve->test(dsumv)) {
					see(v);
					sum = sumv;
					dsum = dsumv;
					return v;
				}
			}
		}
	}
}

int main() {
	long long pc = 0;
	sieve = new bitset<MAXPRIME>;
	sieve->set(0);
	sieve->set(1);
	for (long long n=2; n<MAXPRIME; n++) {
		if (!sieve->test(n)) {
			pc++;
			for (long long m=2*n; m<MAXPRIME; m+=n) {
				sieve->set(m);
			}
		}
	}

	cerr << "# got " << pc << " primes up to " << MAXPRIME << endl;

	for (int n=1; n<=10000; n++) {
		cout << n << " " << other() << endl;
	}

	return 0;
}