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

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

vector<long long> cc;

long long avoid(long long p) {
	if (!seen->test(1)) {
		return 1;
	}

	long long w=1;
	for (long long b=2;; 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->test(c)) {
					return c;
				}
			}

			w*=2;
		}
	}
}

#define WANTED 10001

long long a[WANTED];

int main() {
	seen = new bitset<MAX>;
	cc.resize(1);
	cc[0] = 1;	// we will only search for odd terms

	memset(a, 0, sizeof(a));

	for (int n=0; n<WANTED; n++) {
		if (n==0) {
			a[n] = 0;
		} else if (n%2) {
			a[n] = avoid(a[n-1] | a[n+1]);
			seen->set(a[n]);
		}

		if (n) {
			for (int m=2*n; m<WANTED; m++) {
				a[m] = 2*a[m/2];
			}
		}

		cout << n << ' ' << a[n] << endl;
	}

	delete seen;

	return 0;
}