#include <bitset>
#include <iostream>
#include <string.h>
using namespace std;

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 mm = 0;	// greatest value
long long m = 0;	// second greatest value

#define MAX (1LL<<30)
bitset<MAX> *seen = 0;
long long unseen = 1;

long long n = 0;
bool emit(long long v) {
	seen->set(v);

	cout << ++n << ' ' << v << endl;

	if (mm<v) {
		m=mm;
		mm=v;
		return true;	// restart scan as mm+m has changed
	} else if (m<v) {
		m=v;
		return true;	// go on
	} else {
		return false;	// go on
	}
}

int main() {
	seen = new bitset<MAX>;

	emit(1);
	emit(2);

	long n0;
	do {
		n0 = n;
		long long x = mm + m;

		while (seen->test(unseen)) {
			unseen++;
		}

		for (long long v=unseen; n<10000 && v<MAX; v++) {
			if (!seen->test(v) && gcd(v, x)>1) {
				if (emit(v)) {
					break;
				}
			}
		}
	} while (n0 < n);

	delete seen;

	return 0;
}