#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

#define MAX 858026	// a(10000) + 1

bitset<MAX> *seen = 0;

void sieveOut(long long x, long long y) {
	long long xy;
	while ((xy = x+y)<MAX) {
		seen->set(xy);
		x = y;
		y = xy;
	}
}

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

	vector<long long> a;
	for (long long v=1; v<MAX; v++) {
		if (!seen->test(v)) {
			a.push_back(v);
			cout << a.size() << ' ' << v << endl;

			for (size_t k=0; k<a.size(); k++) {
				sieveOut(a[k], v);
				sieveOut(v, a[k]);
			}
		}
	}

	delete seen;
	return 0;
}