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

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

bitset<MAX*MAX> *grid = 0;

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

vector<long long> genbl;	// bottom left
vector<long long> gentr;	// top right
vector<long long> newgenbl;
vector<long long> newgentr;

void check(long long x, long long y) {
	if (!get(x,y)) {
		long long minx=x, maxx=x, miny=y, maxy=y;
		while (!get(minx-1, y)) {
			minx--;
		}
		while (!get(maxx+1, y)) {
			maxx++;
		}
		while (!get(x, miny-1)) {
			miny--;
		}
		while (!get(x, maxy+1)) {
			maxy++;
		}

		for (long long xx=minx; xx<=maxx; xx++) {
			for (long long yy=miny; yy<=maxy; yy++) {
				set(xx, yy);
			}
		}

		newgenbl.push_back(encode(minx, miny));
		newgentr.push_back(encode(maxx, maxy));
	}
}

void explore(long long bl, long long tr) {
	long long minx, maxx, miny, maxy;
	decode(bl, minx, miny);
	decode(tr, maxx, maxy);

	for (long long x=minx; x<=maxx; x++) {
		check(x, miny-2);
		check(x, maxy+2);
	}
	for (long long y=miny; y<=maxy; y++) {
		check(minx-2, y);
		check(maxx+2, y);
	}
}

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

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

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

	for (long long n=1; n<=ITER; n++) {
		// cut vertically
		for (long long x = s/2; x<MAX; x+=s) {
			bool prec = false;
			bool write = false;
			for (long long 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 (long long y = s/2; y<MAX; y+=s) {
			bool prec = false;
			bool write = false;
			for (long long 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;
	}

	genbl.push_back(encode(1,1));
	gentr.push_back(encode(1,1));
	set(1,1);
	cout << 0 << ' ' << genbl.size() << endl;

	for (long long n=1;; n++) {
		for (size_t k=0; k<genbl.size(); k++) {
			explore(genbl[k], gentr[k]);
		}

		genbl = newgenbl;
		gentr = newgentr;
		newgenbl.clear();
		newgentr.clear();

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

	return 0;
}