#include <bitset>
#include <iostream>
#include <vector>
using namespace std;

#define MAX (1LL<<25)
bitset<MAX> *seen = 0;

vector<long long> cc;

long long other(long long p) {
	seen->set(p);

	long long w=1;
	for (long long b=1;; b<<=1) {
		if ((p & b)==0) {
			if (cc.size()==w) {
				cc.resize(2*w);
			}

			for (long long k=0; k<w; k++) {
				long long c = cc[w+k] = b + cc[k];
				if (c >= MAX) {
					return -1;
				}
				if (!seen->test(c)) {
					return c;
				}
			}

			w*=2;
		}
	}
}

#define WANTED	10001
long long a[WANTED];

int main() {
	seen = new bitset<MAX>;
	seen->set(0);	// only positive integers
	cc.resize(1);

	long long v=1;
	for (long long n=1; v>0 && n<WANTED; n++) {
		a[n] = v;

		long long nb = 0;
		for (long long m=1; m<=n; m++) {
			if ((a[m] & a[n])==0) {
				nb++;
			}
		}

		cout << n << ' ' << nb << endl;
		
		v = other(v);
	}

	delete seen;

	return 0;
}