#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) {
	// powers of 2
	if (i==0) {
		return 1;
	} else {
		return 2*get(i-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 1048575+1
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;
}