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

union long2int {
	long long ll;
	int       i[2];
};

long long encode(const int x, const int y) {
	long2int l2i;
	l2i.i[0] = x;
	l2i.i[1] = y;
	return l2i.ll;
}

void decode(const long long ll, int &x, int &y) {
	long2int l2i;
	l2i.ll = ll;
	x = l2i.i[0];
	y = l2i.i[1];
}

// visited states
unordered_set<long long> visited;

// go backwards to unsivited states
void backwards(long long pos, unordered_set<long long> &positions) {
	int v, x;
	decode(pos, v, x);

	for (int d=-1; d<=+1; d++) {
		long long b = encode(v+d, x-v);
		if (!visited.count(b)) {
			positions.insert(b);
		}
	}
}

// A360926		Smallest number of moves needed to win Integer Lunar Lander with a starting position of (n,n).
#define MAX		2000
int a[MAX];

int main() {
	memset(a, -1, sizeof(a));
	int u=0;

	// positions at distance n
	unordered_set<long long> w;
	w.insert(0);

	for (int n=0;; n++) {
		// set everything as seen
		for (long long pos : w) {
			visited.insert(pos);
			int v, x;
			decode(pos, v,x);
			if (v==x && x>=0 && x<MAX) {
				a[x] = n;
			}
		}

		while (a[u]>=0) {
			cout << u << ' ' << a[u] << endl;
			u++;
			if (u==MAX) {
				goto theEnd;
			}
		}

		// go backwards
		unordered_set<long long> before;
		for (long long pos : w) {
			backwards(pos, before);
		}

		w = before;
	}

theEnd:
	return 0;
}