#include <iostream>
#include <vector>

constexpr int mx = 12'349'201;
std::vector<int> a;
std::vector<int> idx(mx);

void mark(int n, int x, int y) {
	if (idx[x]==0) {
		idx[x] = n;
	}

	if (idx[y]==0) {
		idx[y] = n;
	}

	int xy = x+y;
	if (xy && xy < mx) {
		mark(n, y, xy);
	}
}

int main() {
	int n = 0;

	for (int v = 0; v < mx; v++) {
		if (idx[v]==0) {
			std::cout << ++n << ' ' << v << std::endl;
			a.push_back(v);

			for (const auto & w : a) {
				mark(n, w, v);
			}
		}
	}

	return 0;
}