#include <iostream>
#include <vector>
#include <cmath>

int main() {
	std::vector<int> a(10001);
	std::vector<int> forbidden(1, -1);

	for (int n = 0; n<a.size(); n++) {
		if (n) {
			// 0...0...0
			forbidden[0] = n;
		}

		// mark other forbidden values
		for (int m = n-2; m > -n; m-=2) {
			int f = a[abs(m)];
			if (a[abs((m+n)/2)] == f) {
				while (f >= forbidden.size()) {
					forbidden.resize(2 * forbidden.size(), -1);
				}
				forbidden[f] = n;
			}
		}

		while (a[n] < forbidden.size() && forbidden[a[n]]==n) {
			a[n]++;
		}

		std::cout << n << ' ' << a[n] << std::endl;
	}

	return 0;
}