#include <algorithm>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

typedef unsigned long long ull;
typedef __uint128_t ulll;

/*

Key idea is similar to https://oeis.org/A340043/a340043_1.txt.

In the DP state, besides 0~4, 5 is also used to indicate "connected to end of
the path".

*/

// saves current connecttivity
struct dp_key_t {
  ulll s;
  dp_key_t() {}
  dp_key_t(ulll v) { s = v; }

  // get status of x-th point
  int get(int x) const { return s >> x * 3 & 7; }

  // set x-th point to y, and return the new one
  dp_key_t set(int x, int y) const {
    ulll v = (s & ~(ulll(7) << x * 3)) | ulll(y) << x * 3;
    return dp_key_t(v);
  }

  // insert y at left, and return the new one
  dp_key_t ins(int x) const {
    ulll v = x | s << 3;
    return dp_key_t(v);
  }

  // return the position of matched ")" of some "("
  int rmatch(int x) const {
    int c = 1;
    for (x++;; x++) {
      int t = get(x);
      if (t == 1)
        c++;
      else if (t == 2)
        c--;
      if (!c)
        return x;
    }
  }

  // return the position of matched "(" of some ")"
  int lmatch(int x) const {
    int c = 1;
    for (x--;; x--) {
      int t = get(x);
      if (t == 2)
        c++;
      else if (t == 1)
        c--;
      if (!c)
        return x;
    }
  }

  std::pair<int, int> estimate() const {
    ulll t = s;
    int cnt = 0;
    bool count_ans = true, any3 = false;
    while (t) {
      int x = t & 7;
      cnt += x != 0 && x != 4, t >>= 3;
      if (x != 0 && x != 4)
        count_ans = false;
      if (x == 3)
        any3 = true;
    }
    return std::make_pair(cnt >> 1, int(count_ans) << 1 | int(any3));
    ;
  }

  bool operator==(const dp_key_t &o) const { return s == o.s; }
};

struct hash {
  size_t operator()(const dp_key_t &x) const { return x.s; }
};

// f is dp[current state], g is dp[next state]
std::unordered_map<dp_key_t, ull, hash> f[1000], g[1000];

// n is used to cut unnecessary states
int glo_n;
std::vector<ull> ans;

// here expected_edges is used to ensure thread safety (one thread only works
// for one expected_edges)
void addg(int real_edges, int expected_edges, const dp_key_t &a, const ull &b) {
  if (expected_edges == real_edges) {
    auto t = a.estimate();
    if (t.second & 2) {
      if (real_edges <= glo_n)
        ans[real_edges] += b;
    } else if (t.second & 1) {
      // each pair of remaining unconnected line needs at least 2 edges to be
      // connected
      if (real_edges + t.first * 2 <= glo_n)
        g[real_edges][a] += b;
    }
  }
}

/*
ltrans:
. . . .     * . . .
* . . .     * . . .
. * . . --> . * . .
. . * .     . . * .
. . . *     . . . *
*/
void ltrans(const dp_key_t &a, const ull &b, int n, int edges, int expedges) {
  int t = a.get(0);
  addg(edges, expedges, a.ins(0), b);
  if (t == 0)
    addg(edges + 1, expedges, a.set(0, 2).ins(1), b);
  else if (t != 4)
    addg(edges + 1, expedges, a.set(0, 4).ins(t), b);
}

/*
rtrans:
* . . . . .     * . . . . .
. * . . . . --> . * . . . .
. * . . . .     . . * . . .
*/
void rtrans(const dp_key_t &a, const ull &b, int x, int edges, int expedges) {
  int t = a.get(x);
  bool no5 = 1;
  for (int i = 0; i <= x; i++) {
    if (a.get(i) == 5)
      no5 = 0;
  }
  if (t == 0 || t == 4 || (t == 3 && no5))
    addg(edges, expedges, a.set(x, 0), b);
  else if (t == 2)
    addg(edges, expedges, a.set(a.lmatch(x), 5).set(x, 0), b);
  if (t != 0 && t != 4)
    addg(edges + 1, expedges, a, b);
  if (t == 0 && no5)
    addg(edges + 1, expedges, a.set(x, 5), b);
}

/*
normal transition (as the initial definition)
* . . . .     * . . . .
. * . . .     . * . . .
. . * . . --> . . * . .
. . * . .     . . . * .
. . . * .     . . . * .
*/
void transition(const dp_key_t &a, const ull &b, int p, int n, int edges,
                int expedges) {
  bool no5 = 1;
  for (int i = 0; i < n; i++) {
    int t = a.get(i);
    if (t == 5)
      no5 = 0;
  }
  int x = a.get(p), y = a.get(p + 1);
  if (x == 4)
    addg(edges, expedges, a.set(p, 0), b);
  else if (x == 0) {
    addg(edges, expedges, a, b);
    if (no5)
      addg(edges + 1, expedges, a.set(p, 5), b);
  } else {
    addg(edges + 1, expedges, a, b);
    if (no5) {
      if (x == 1)
        addg(edges, expedges, a.set(a.rmatch(p), 5).set(p, 0), b);
      else if (x == 2)
        addg(edges, expedges, a.set(a.lmatch(p), 5).set(p, 0), b);
      else if (x == 3)
        addg(edges, expedges, a.set(p, 0), b);
    }
  }
  if (x == 0 || x == 4) {
    if (y == 0) {
      addg(edges + 1, expedges, a.set(p, 1).set(p + 1, 2), b);
    } else if (y != 4) {
      addg(edges + 1, expedges, a.set(p, y).set(p + 1, 4), b);
    }
  } else if (x == 1) {
    if (no5) {
      dp_key_t ta = a.set(a.rmatch(p), 5);
      if (y == 0) {
        addg(edges + 1, expedges, ta.set(p, 1).set(p + 1, 2), b);
      } else if (y == 2) {
        addg(edges + 1, expedges, a.set(p, 5).set(p + 1, 4), b);
      } else if (y != 4) {
        addg(edges + 1, expedges, ta.set(p, y).set(p + 1, 4), b);
      }
    }
  } else if (x == 2) {
    if (no5) {
      dp_key_t ta = a.set(a.lmatch(p), 5);
      if (y == 0) {
        addg(edges + 1, expedges, ta.set(p, 1).set(p + 1, 2), b);
      } else if (y != 4) {
        addg(edges + 1, expedges, ta.set(p, y).set(p + 1, 4), b);
      }
    }
  } else if (x == 3) {
    if (no5) {
      dp_key_t ta = a;
      if (y == 0) {
        addg(edges + 1, expedges, ta.set(p, 1).set(p + 1, 2), b);
      } else if (y != 4) {
        addg(edges + 1, expedges, ta.set(p, y).set(p + 1, 4), b);
      }
    }
  }
  if (x == 1) {
    if (y == 0) {
      addg(edges + 2, expedges, a.set(p, 4).set(p + 1, 1), b);
    } else if (y == 1) {
      addg(edges + 2, expedges,
           a.set(a.rmatch(p + 1), 1).set(p, 4).set(p + 1, 4), b);
    } else if (y == 3 || y == 5) {
      addg(edges + 2, expedges, a.set(a.rmatch(p), y).set(p, 4).set(p + 1, 4),
           b);
    }
  } else if (x == 2) {
    if (y == 0) {
      addg(edges + 2, expedges, a.set(p, 4).set(p + 1, 2), b);
    } else if (y == 1) {
      addg(edges + 2, expedges, a.set(p, 4).set(p + 1, 4), b);
    } else if (y == 2) {
      addg(edges + 2, expedges, a.set(a.lmatch(p), 2).set(p, 4).set(p + 1, 4),
           b);
    } else if (y == 3 || y == 5) {
      addg(edges + 2, expedges, a.set(a.lmatch(p), y).set(p, 4).set(p + 1, 4),
           b);
    }
  } else if (x == 3) {
    if (y == 0) {
      addg(edges + 2, expedges, a.set(p, 4).set(p + 1, 3), b);
    } else if (y == 1) {
      addg(edges + 2, expedges,
           a.set(a.rmatch(p + 1), 3).set(p, 4).set(p + 1, 4), b);
    } else if (y == 2) {
      addg(edges + 2, expedges,
           a.set(a.lmatch(p + 1), 3).set(p, 4).set(p + 1, 4), b);
    } else if (y == 5) {
      addg(edges + 2, expedges, a.set(p, 4).set(p + 1, 4), b);
    }
  } else if (x == 5 || (x == 0 && no5)) {
    if (y == 0) {
      addg(edges + 2, expedges, a.set(p, 4).set(p + 1, 5), b);
    } else if (y == 1) {
      addg(edges + 2, expedges,
           a.set(a.rmatch(p + 1), 5).set(p, 4).set(p + 1, 4), b);
    } else if (y == 2) {
      addg(edges + 2, expedges,
           a.set(a.lmatch(p + 1), 5).set(p, 4).set(p + 1, 4), b);
    } else if (y == 3) {
      addg(edges + 2, expedges, a.set(p, 4).set(p + 1, 4), b);
    }
  }
}

std::vector<ull> solve(int n) {
  f[1][dp_key_t(3)] = 1;
  glo_n = n;

  // get current min and max of number of edges
  auto getlr = [&](int &l, int &r, int maxr) {
    l = 0, r = maxr;
    while (l < maxr && !f[l].size())
      l++;
    while (r > 0 && !f[r].size())
      r--;
  };

  // parallelly run DP for a given transition function
  auto pawork =
      [&](std::function<void(const dp_key_t &, const ull &, int, int)> trans,
          int rn) {
        int l, r;
        getlr(l, r, n);

#pragma omp parallel for num_threads(15)
        for (int i = l; i <= std::min(r + 2, n); i++) {
          for (int j = i > 2 ? i - 2 : 0; j <= i; j++)
            for (auto &o : f[j])
              trans(o.first, o.second, j, i);
        }

#pragma omp parallel for num_threads(15)
        for (int i = l; i <= std::min(r + 2, n); i++) {
          f[i].swap(g[i]);
          g[i].clear();
        }
      };

  ans.clear();
  for (int i = 0; i <= n; i++)
    ans.push_back(0);

  for (int i = 2; i <= n + 1; i++) {
    std::cerr << "working: " << i << " ltrans" << std::endl;
    pawork([&](const dp_key_t &a, const ull &b, int c,
               int d) { ltrans(a, b, i, c, d); },
           i + 1);
    for (int j = 1; j < i; j++) {
      std::cerr << "working: " << i << " trans " << j << std::endl;
      pawork([&](const dp_key_t &a, const ull &b, int c,
                 int d) { transition(a, b, j, i + 1, c, d); },
             i + 1);
    }
    std::cerr << "working: " << i << " rtrans" << std::endl;
    pawork([&](const dp_key_t &a, const ull &b, int c,
               int d) { rtrans(a, b, i, c, d); },
           i + 1);
  }
  return ans;
}

int main(int argc, char **argv) {
  int n = atoi(argv[1]);
  std::vector<ull> ans = solve(n);
  for (int i = 1; i <= n; i++) {
    std::cout << i << " " << ans[i] << std::endl;
  }
}