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

#define ITER    14
#define MAX 	(2LL<<ITER)

bitset<MAX*MAX> *grid = 0;

int encode(int x, int y) {
	return x*MAX + y;
}
void decode(int c, int &x, int &y) {
	x = c/MAX;
	y = c%MAX;
}
bool get(int x, int y) {
	if (x<0 || y<0) {
		return false;
	} else if (x>=MAX || y>=MAX) {
		// the end
		exit(0);
	} else {
		return grid->test(encode(x,y));
	}
}
bool atCorner(int x, int y) {
	if ((get(x-1,y) || get(x+1,y)) && (get(x,y-1) || get(x,y+1))) {
		return true;
	} else {
		return false;
	}
}
void set(int x, int y) {
	grid->set(encode(x,y));
}
void reset(int x, int y) {
	grid->reset(encode(x,y));
}

vector<int> gen;
vector<int> newgen;

void explore(int x, int y, int dx, int dy) {
	while (get(x+=dx, y+=dy) && get(x+=dx, y+=dy)) {
		reset(x,y);
		if (atCorner(x,y)) {
			newgen.push_back(encode(x,y));
			return;
		}
	}
}

void explore(int c) {
	int x, y;
	decode(c, x, y);

	explore(x, y, +1, 0);
	explore(x, y, -1, 0);
	explore(x, y, 0, +1);
	explore(x, y, 0, -1);
}

int main() {
	grid = new bitset<MAX*MAX>;

	for (int b=0; b<MAX; b++) {
		set(b,0);
		set(0,b);
	}

	int s = MAX;	// step size
	int r = 1;	// # of rectangles

	for (int n=1; n<=ITER; n++) {
		// cut vertically
		for (int x = s/2; x<MAX; x+=s) {
			bool prec = false;
			bool write = false;
			for (int y = 0; y<MAX; y++) {
				bool curr = get(x,y);

				if (prec && !curr) {
					write = !write;
					if (write) {
						r++;
					}
				}
				if (write) {
					set(x,y);
				}

				prec = curr;
			}
		}

		// cut horizontally
		for (int y = s/2; y<MAX; y+=s) {
			bool prec = false;
			bool write = false;
			for (int x = 0; x<MAX; x++) {
				bool curr = get(x,y);

				if (prec && !curr) {
					write = !write;
					if (write) {
						r++;
					}
				}
				if (write) {
					set(x,y);
				}

				prec = curr;
			}
		}

		s/=2;
	}

	gen.push_back(encode(0,0));
	reset(0,0);
	cout << 0 << ' ' << gen.size() << endl;

	for (int n=1;; n++) {
		for (size_t k=0; k<gen.size(); k++) {
			explore(gen[k]);
		}

		gen = newgen;
		newgen.clear();

		cout << n << ' ' << gen.size() << endl;
	}

	return 0;
}