using System;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;

namespace PaperFoldingRegions {
    class Program {
        static void Main(string[] args) {
            long[] a = new long[1 + 2 * N];
            for (int x = 0; x < Max; x++) {
                for (int y = 0; y < Max; y++) {
                    if (!visited[x][y]) {
                        Point p = new Point(x, y);
                        a[Rank(p)]++;

                        Queue<Point> visiting = new Queue<Point>();
                        visiting.Enqueue(p);
                        visited[p.X][p.Y] = true;

                        while (visiting.Count>0) {
                            foreach (Point q in SquareNeighbours(visiting.Dequeue())) {
                                if (!visited[q.X][q.Y]) {
                                    visiting.Enqueue(q);
                                    visited[q.X][q.Y] = true;
                                }
                            }
                        }
                    }
                }
            }

            long s = 0;
            for (int n = 0; n < a.Length; n++) {
                Console.WriteLine($"{n} {s += a[n]}");
            }
        }

        static int Rank(Point p) {
            return 2 * Math.Max(bits[p.X], bits[p.Y]) - (bits[p.X] < bits[p.Y] ? 1 : 0);
        }

        static IEnumerable<Point> SquareNeighbours(Point p) {
            if (RightSquare(p)) {
                yield return new Point(p.X + 1, p.Y);
            }
            if (UpSquare(p)) {
                yield return new Point(p.X, p.Y + 1);
            }
            if (LeftSquare(p)) {
                yield return new Point(p.X - 1, p.Y);
            }
            if (DownSquare(p)) {
                yield return new Point(p.X, p.Y - 1);
            }
        }

        // Right - left - up - down square connected to square at p?
        static bool RightSquare(Point p) {
            return !Up(new Point(p.X + 1, p.Y));
        }
        static bool LeftSquare(Point p) {
            return !Up(p);
        }
        static bool UpSquare(Point p) {
            return !Right(new Point(p.X, p.Y + 1));
        }
        static bool DownSquare(Point p) {
            return !Right(p);
        }

        // Right - left - up - down point connected to point at p?
        static bool Right(Point p) {
            if (p.X < 0 || p.Y < 0) {
                return false;
            } else if (p.Y == 0) {
                return true;
            } else {
                return (p.X >> val2[p.Y]) % 2 != pf[p.Y];
            }
        }
        static bool Left(Point p) {
            return Right(new Point(p.X - 1, p.Y));
        }
        static bool Up(Point p) {
            if (p.X < 0 || p.Y < 0) {
                return false;
            } else if (p.X == 0) {
                return true;
            } else {
                return (p.Y >> (val2[p.X] + 1)) % 2 != pf[p.X];
            }
        }
        static bool Down(Point p) {
            return Up(new Point(p.X, p.Y - 1));
        }

        const int N = 15;                               // maximum number of double-folds
        const int Max = 1 << N;
        static readonly int[] val2 = new int[Max + 1];  // 2-adic valuation ~ A007814
        static readonly int[] pf = new int[Max + 1];    // regular paper-folding sequence ~ A014577 with a leading 0
        static readonly int[] bits = new int[Max + 1];  // number of bits ~ A070939 with a(0) = 0
        static readonly BitArray[] visited = new BitArray[Max];
        static Program() {
            val2[0] = int.MaxValue;
            pf[0] = 0;
            bits[0] = 0;
            for (int n = 1; n <= Max; n++) {
                int m = n;
                while (m % 2 == 0) {
                    val2[n]++;
                    m /= 2;
                }
                if ((m & 2) == 0) {
                    pf[n] = 1;
                }
                if (n == 1) {
                    bits[n] = 1;
                } else {
                    bits[n] = 1 + bits[n / 2];
                }
            }

            for (int x = 0; x < Max; x++) {
                visited[x] = new BitArray(Max);
            }
        }
    }
}