using System;
using System.Collections.Generic;
using System.Linq;

namespace A342169 {
    class Program {
        static void Main(string[] args) {
            Dictionary<int, Tile> gen = new Dictionary<int, Tile>();
            Tile seed = Tiling.Get(1, 0).Tile;
            gen[seed.Index] = seed;

            for (int n = 0; n <= 5000; n++) {
                Console.WriteLine($"{n} {gen.Count}");

                foreach (Tile tile in gen.Values) {
                    tile.Visited = true;

                    //Tiling.Get(tile.Right.X + 2, tile.Right.Y);
                }

                Dictionary<int, Tile> newgen = new Dictionary<int, Tile>();
                foreach (Tile tile in gen.Values) {
                    foreach (Tile neighbor in tile.Neighbours) {
                        if (neighbor != null && !neighbor.Visited) {
                            newgen[neighbor.Index] = neighbor;
                        }
                    }
                }

                gen = newgen;
            }
        }
    }

    class Tiling {
        public static Square Get(int x, int y) {
            if (y < 0) {
                return null;
            } else {
                while (y >= rows.Count) {
                    rows.Add(new Row() { Y = rows[rows.Count - 1].Y + 1, Previous = rows[rows.Count - 1] });
                }
                return rows[y].Get(x);
            }
        }

        private static readonly List<Row> rows = new List<Row>();
        static Tiling() {
            rows.Add(new Row());
            rows[0].row.Add(new Start());
        }
    }

    class Square {
        public int X { get; set; }
        public int Y { get; set; }
        public Tile Tile { get; set; }
    }
    class Top : Square {
    }
    class Left : Square {
    }
    class Right : Square {
    }
    class Empty : Square {
    }
    class Start : Square {
    }

    class Tile {
        public int Index { get; private set; } = ++Counter;
        public Top Top { get; set; }
        public Left Left { get; set; }
        public Right Right { get; set; }
        public bool Visited { get; set; }
        public IEnumerable<Tile> Neighbours {
            get {
                Tiling.Get(this.Right.X, this.Right.Y + 1);    // ensure Top is known

                yield return Tiling.Get(this.Left.X - 1, this.Left.Y)?.Tile;
                yield return Tiling.Get(this.Left.X, this.Left.Y - 1)?.Tile;
                yield return Tiling.Get(this.Right.X + 1, this.Right.Y)?.Tile;
                yield return Tiling.Get(this.Right.X, this.Right.Y - 1)?.Tile;
                yield return Tiling.Get(this.Top.X - 1, this.Top.Y)?.Tile;
                yield return Tiling.Get(this.Top.X, this.Top.Y + 1)?.Tile;
                yield return Tiling.Get(this.Top.X + 1, this.Top.Y)?.Tile;
            }
        }
        private static int Counter = 0;
    }

    class Row {
        public int Y { get; set; }
        public Row Previous { get; set; }
        public Square Get(int x) {
            if (x < 0) {
                return null;
            } else {
                while (x >= this.row.Count) {
                    int xx = this.row.Count;
                    if (this.Previous == null) {
                        Tile tile = new Tile();
                        tile.Left = new Left() {
                            X = xx,
                            Y = this.Y,
                            Tile = tile,
                        };
                        tile.Right = new Right() {
                            X = xx + 1,
                            Y = this.Y,
                            Tile = tile,
                        };
                        this.row.Add(tile.Left);
                        this.row.Add(tile.Right);
                    } else {
                        if (this.Previous.Get(xx) is Top) {
                            if (this.Previous.Get(xx + 1) is Top) {
                                Tile tile = new Tile();
                                tile.Left = new Left() {
                                    X = xx,
                                    Y = this.Y,
                                    Tile = tile,
                                };
                                tile.Right = new Right() {
                                    X = xx + 1,
                                    Y = this.Y,
                                    Tile = tile,
                                };
                                this.row.Add(tile.Left);
                                this.row.Add(tile.Right);
                            } else {
                                Tile tile = new Tile();
                                tile.Left = new Left() {
                                    X = xx,
                                    Y = this.Y,
                                    Tile = tile,
                                };
                                tile.Right = new Right() {
                                    X = xx + 1,
                                    Y = this.Y,
                                    Tile = tile,
                                };
                                Top top = new Top() {
                                    X = xx + 2,
                                    Y = this.Y,
                                    Tile = this.Previous.Get(xx + 1).Tile,
                                };
                                top.Tile.Top = top;
                                this.row.Add(tile.Left);
                                this.row.Add(tile.Right);
                                this.row.Add(top);
                            }
                        } else if (this.Previous.Get(xx) is Left) {
                            if (this.Previous.Get(xx + 2) is Top) {
                                Top top = new Top() {
                                    X = xx,
                                    Y = this.Y,
                                    Tile = this.Previous.Get(xx).Tile,
                                };
                                top.Tile.Top = top;
                                Tile tile = new Tile();
                                tile.Left = new Left() {
                                    X = xx + 1,
                                    Y = this.Y,
                                    Tile = tile,
                                };
                                tile.Right = new Right() {
                                    X = xx + 2,
                                    Y = this.Y,
                                    Tile = tile,
                                };
                                this.row.Add(top);
                                this.row.Add(tile.Left);
                                this.row.Add(tile.Right);
                            } else {
                                Top top1 = new Top() {
                                    X = xx,
                                    Y = this.Y,
                                    Tile = this.Previous.Get(xx).Tile,
                                };
                                top1.Tile.Top = top1;
                                Tile tile = new Tile();
                                tile.Left = new Left() {
                                    X = xx + 1,
                                    Y = this.Y,
                                    Tile = tile,
                                };
                                tile.Right = new Right() {
                                    X = xx + 2,
                                    Y = this.Y,
                                    Tile = tile,
                                };
                                Top top2 = new Top() {
                                    X = xx + 3,
                                    Y = this.Y,
                                    Tile = this.Previous.Get(xx + 3).Tile,
                                };
                                top2.Tile.Top = top2;
                                this.row.Add(top1);
                                this.row.Add(tile.Left);
                                this.row.Add(tile.Right);
                                this.row.Add(top2);
                            }
                        } else if (this.Previous.Get(xx) is Start) {
                            if (this.Previous.Get(xx + 1) is Top) {
                                Empty empty = new Empty() {
                                    X = xx,
                                    Y = this.Y,
                                };
                                Start start = new Start() {
                                    X = xx + 1,
                                    Y = this.Y,
                                };
                                this.row.Add(empty);
                                this.row.Add(start);
                            } else {
                                Empty empty = new Empty() {
                                    X = xx,
                                    Y = this.Y,
                                };
                                Start start = new Start() {
                                    X = xx + 1,
                                    Y = this.Y,
                                };
                                Top top = new Top() {
                                    X = xx + 2,
                                    Y = this.Y,
                                    Tile = this.Previous.Get(xx + 1).Tile,
                                };
                                top.Tile.Top = top;
                                this.row.Add(empty);
                                this.row.Add(start);
                                this.row.Add(top);
                            }
                        } else if (this.Previous.Get(xx) is Empty) {
                            Empty empty = new Empty() {
                                X = xx,
                                Y = this.Y,
                            };
                            this.row.Add(empty);
                        } else {
                            throw new Exception("bug");
                        }
                    }
                }
                return this.row[x];
            }
        }
        internal readonly List<Square> row = new List<Square>();
    }
}