#include <limits.h>
#include <stdio.h>
#include <string.h>

#define MAX 10001
int a[MAX];

#define DEPTH 30

void explore(long long u, long long v, int depth) {
	if (v>=0 && v<MAX && a[v]>depth) {
		a[v] = depth;
	}

	depth++;
	if (depth<=DEPTH) {
		explore(v, v+u, depth);
		explore(v, v-u, depth);
	}
}

int main() {
	for (int n=0; n<MAX; n++) {
		a[n] = INT_MAX;
	}
	a[0] = 0;

	explore(0, 1, 1);

	for (int n=0; n<MAX; n++) {
		if (a[n]==INT_MAX) {
			break;
		} else {
			printf("%d %d\n", n, a[n]);
		}
	}

	return 0;
}