#include <stdio.h>

#define MAX 2500001


long long a[MAX];

int main() {
	for (long long n=1; n<MAX; n++) {
		for (long long k=1; n-1-2*k>0; k++) {
			if (2*a[n-1-k]==a[n-1]+a[n-1-2*k]) {
				a[n]++;
			}
		}
		printf ("%lld %lld\n", n, a[n]);
		fflush(stdout);
	}
	return 0;
}