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

#define MAX (1+10000)

int a[MAX];
int o[MAX];

void explore(int index, int x, int y) {
	int xy = x+y;
	if (xy<MAX) {
		if (a[xy] < index) {
			a[xy] = index;
		}
		explore(index+1, y, xy);
	}
}

int main() {
	memset(a, 0, sizeof(a));
	memset(o, 0, sizeof(o));

	for (int f0=0; f0<MAX; f0++) {
		for (int f1=0; f1<MAX; f1++) {
			if (f0 || f1) {
				explore(2, f0, f1);
			}
		}
	}

	for (int n=1; n<MAX; n++) {
		printf("%d %d\n", n, ++o[a[n]]);
	}

	return 0;
}