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

#define MAX (1LL<<32)

long long get(long long i);
long long compute(long long i) {
	// Catalan numbers
	switch (i) {
		case 0: return 1LL;
		case 1: return 1LL;
		case 2: return 2LL;
		case 3: return 5LL;
		case 4: return 14LL;
		case 5: return 42LL;
		case 6: return 132LL;
		case 7: return 429LL;
		case 8: return 1430LL;
		case 9: return 4862LL;
		case 10: return 16796LL;
		case 11: return 58786LL;
		case 12: return 208012LL;
		case 13: return 742900LL;
		case 14: return 2674440LL;
		case 15: return 9694845LL;
		case 16: return 35357670LL;
		case 17: return 129644790LL;
		case 18: return 477638700LL;
		case 19: return 1767263190LL;
		case 20: return 6564120420LL;
		case 21: return 24466267020LL;
		case 22: return 91482563640LL;
		case 23: return 343059613650LL;
		case 24: return 1289904147324LL;
		case 25: return 4861946401452LL;
		case 26: return 18367353072152LL;
		case 27: return 69533550916004LL;
		case 28: return 263747951750360LL;
		case 29: return 1002242216651368LL;
		case 30: return 3814986502092304LL;
		default: exit(1);
	}
}

vector<long long> f;
long long get(long long i) {
	while (i>=f.size()) {
		f.push_back(compute(f.size()));
	}
	return f[i]; 
}

#define NB 16796
long long nb[NB];

int main() {
	bool *sums = new bool[MAX];

	memset(sums, 0, MAX*sizeof(*sums));
	sums[0] = true;

	memset(nb, 0, sizeof(nb));
	nb[0] = 1;

	long long total = 0;
	long long limit = 0;
	long long n = 0;

	for (long long v=1; v<NB; v++) {
		while (get(limit) < v+total) {
			limit++;
		}

		bool keep = true;

		long long d;
		for (long long t=limit; (d=get(t)-v)>=0; t--) {
			if (d<MAX && sums[d]) {
				keep = false;
				break;
			}
		}

		if (keep) {
			for (long long o=total; o>=0; o--) {
				if (sums[o]) {
					if (o+v>=MAX) {
						delete[] sums;
						return 1;
					}

					sums[o+v] = true;

					if (o+v<NB) {
						nb[o+v]+=nb[o];
					}
				}
			}

			total += v;
		}
	}

	for (long long n=0; n<NB; n++) {
		cout << n << ' ' << nb[n] << endl;
	}

	delete[] sums;
	return 0;
}