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

using namespace std;

#define MAX    (1LL<<30)
#define SMALL  (1LL<<35)

class Arit {
public:
	Arit(long long n, long long v) : _min(n), _mod(v), _max(n+(v-1)*v) {}

	bool contains(long long v) {
		if (v>=_min && v<=_max && (v-_min)%_mod==0) {
			return true;
		} else {
			return false;
		}
	}

private:
	const long long _min;
	const long long _mod;
	const long long _max;
};

bitset<SMALL> *small = 0;
vector<Arit*>  big;

bool test(long long n) {
	if (n<SMALL) {
		return small->test(n);
	} else {
		for (size_t i=0; i<big.size(); i++) {
			if (big[i]->contains(n)) {
				return true;
			}
		}

		return false;
	}
}

map<long,bool> seen;
#define WANTED 5001LL
long long a[WANTED];

void set(long long n, long long v) {
	long long min = n;
	long long max = n + (v-1)*v;

	seen[v] = true;

	for (long long n=min; n<=max && n<SMALL; n+=v) {
		small->set(n);
		if (n<WANTED) {
			a[n] = v;
		}
	}
	if (max>=SMALL) {
		big.push_back(new Arit(n, v));
	}
}

int main() {
	small = new bitset<SMALL>;
	memset(a, 0, sizeof(a));

	for (long long n=1; n<MAX; n++) {
		if (a[n]==0) {
			for (long long v=1; v<MAX; v++) {
				if (!seen.count(v)) {
					bool ok = true;

					long long m = n;
					for (long long k=v; k>0; k--) {
						if (test(m)) {
							ok = false;
							break;
						}

						m += v;
					}

					if (ok) {
						set(n, v);
						break;
					}
				}
			}
		}

		if (a[n]==0) {
			break;
		} else {
			cout << n << ' ' << a[n] << endl;
		}
	}

	delete small;
	small = 0;

	for (size_t i=0; i<big.size(); i++) {
		delete big[i];
	}
	big.clear();

	return 0;
}