#include <climits>
#include <iostream>
#include <unordered_set>
using namespace std;

// values with Hammingweight 2
unordered_set<long long> seen;

// free bits
long long nbFreeBits = 0;
long long freeBits[6];

// encode
long long encode(long long x, long long y) {
	if (x > y) {
		return (x<<32) + y;
	} else {
		return (y<<32) + x;
	}
}

void notice(long long x) {
	freeBits[nbFreeBits++] = x;
}

void remove(long long x) {
	for (long long k=0; k<nbFreeBits; k++) {
		if (freeBits[k]==x) {
			if (nbFreeBits) {
				freeBits[k] = freeBits[nbFreeBits-1];
			}
			nbFreeBits--;
			return;
		}
	}
}

#define MAX 50000
long long *a = 0;

int main() {
	long long next2 = 1;	// next free bit (LSB = 1)
	long long k = 0;

	a = new long long[MAX];
	for (long long n=1; n<MAX; n++) {
		long long v = LLONG_MAX;
		long long vi, vj;

		// mix of 2 free bits?
		for (long long i=0; i<nbFreeBits; i++) {
			for (long long j=i+1; j<nbFreeBits; j++) {
				long long c = encode(freeBits[i], freeBits[j]);
				if (c < v && !seen.count(c)) {
					vi = freeBits[i];
					vj = freeBits[j];
					v = c;
				}
			}
		}

		// next power of?
		if (v==LLONG_MAX) {
			if (nbFreeBits >= 3) {
				// next value has Hamming weight 3, this was unexpected
				cerr << "# a(" << n << ") has 3 bits!" << endl;
				break;
			}

			v = next2++;
		} else {
			seen.insert(v);

			cout << ++k << ' ' << (vi > vj ? vi : vj)-1 << endl;

			if (k==10000) {
				break;
			}

			remove(vi);
			remove(vj);
		}

		// remember this value
		a[n] = v;

		// new free bits?
		if ((n & 1)==0) {
			long long high = a[n/2] >> 32;
			long long low  = a[n/2] & 0xFFFFFFFF;

			if (high) {
				notice(high);
			}
			if (low) {
				notice(low);
			}
		}
	}

	delete[] a;

	return 0;
}