考虑有根无标号树。对于树的每个顶点，将其子节点划分为一个或多个未命名的组，每个子节点恰好属于一个组。在绘制这样的树时，同一组的子节点在位置上是连续的，并用一条水平线连接。我们将这样的树称为 Catalan 树。下图展示了三棵各有 4 个顶点的 Catalan 树。树从下往上生长。前两棵实际上是同一棵树的不同画法，但最后一棵与它们不同，因为两个根节点的子节点不在同一组中。

Catalan 森林是一组一棵或多棵 Catalan 树的集合。

给定 $n$，求所有树中总共有 $n$ 个顶点的不同 Catalan 森林的数量。

下图展示了所有 14 种包含 4 个顶点的 Catalan 森林。为了清晰起见，同一森林中树的根节点用线连接。树从下往上生长。

输入格式

输入包含多个测试用例。每个测试用例包含一个整数 $n$（$1 \le n \le 60$）。输入的最后一行包含 0，该行无需处理。

输出格式

对于每个测试用例，输出一个数字，即包含 $n$ 个顶点的 Catalan 森林的数量。

样例

输入 1

1
2
3
4
5
0

输出 1

1
2
5
14
42