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

#define MAX (1LL<<34)

bitset<MAX> *seen = 0;
long long unseen = 0;

vector<long long> cc;
long long avoid(long long p) {
	if (!seen->test(0)) {
		return 0;
	}

	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->test(c)) {
					return c;
				}
			}

			w*=2;
		}
	}
}

int main() {
	seen = new bitset<MAX>;
	cc.push_back(0);

	long long pp=0;
	long long p=0;

	long long u = 0;
	long long pr = -1;

	for (long long n=0; u<1000; n++) {
		long long v=avoid(pp+p);

		seen->set(v);

		if (v==unseen) {
			cout << ++u << ' ' << n-pr << endl;

			while (seen->test(unseen)) {
				unseen++;
			}

			pr = n;
		}

		pp=p;
		p=v;
	}

	delete seen;
	seen = 0;

	return 0;
}