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

#define MAX 10001

long long a[MAX];

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

	for (long long n=0; n<MAX; n++) {
		long long p = n-1;
		long long pp = p-1;
		long long ppp = p-2;

		while (ppp >= 0) {
			if (a[ppp] >= a[pp] + a[p]) {
				a[n]++;
			}
			pp -= 1;
			ppp -= 2;
		}

		printf("%lld %lld\n", n, a[n]);
		fflush(stdout);
	}

	return 0;
}