#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) {
	// Pell numbers
	switch (i) {
		case 0: return 0LL;
		case 1: return 1LL;
		case 2: return 2LL;
		case 3: return 5LL;
		case 4: return 12LL;
		case 5: return 29LL;
		case 6: return 70LL;
		case 7: return 169LL;
		case 8: return 408LL;
		case 9: return 985LL;
		case 10: return 2378LL;
		case 11: return 5741LL;
		case 12: return 13860LL;
		case 13: return 33461LL;
		case 14: return 80782LL;
		case 15: return 195025LL;
		case 16: return 470832LL;
		case 17: return 1136689LL;
		case 18: return 2744210LL;
		case 19: return 6625109LL;
		case 20: return 15994428LL;
		case 21: return 38613965LL;
		case 22: return 93222358LL;
		case 23: return 225058681LL;
		case 24: return 543339720LL;
		case 25: return 1311738121LL;
		case 26: return 3166815962LL;
		case 27: return 7645370045LL;
		case 28: return 18457556052LL;
		case 29: return 44560482149LL;
		case 30: return 107578520350LL;
		case 31: return 259717522849LL;
		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 (1LL<<20)
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;
}