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

#define MAX (1LL<<30)
bool *seen = 0;

vector<long long> cc;

long long other(long long 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) {
					exit(1);
				}
				if (!seen[c]) {
					return c;
				}
			}

			w*=2;
		}
	}
}

#define WANTED 100000000

long long a[WANTED];

int main() {
	seen = new bool[MAX];
	memset(seen, 0, MAX * sizeof(bool));
	cc.resize(1);

	long long h=1;
	long long m=0;
	for (long long n=0; n<WANTED; n++) {
		if (n==0) {
			a[n] = 0;
		} else {
			a[n] = other(a[n/2]);
		}

		seen[a[n]] = true;

		if (a[n]==h) {
			cout << ++m << ' ' << n << endl;
			h*=2;
		}
	}

	delete[] seen;

	return 0;
}