1063 - Tree I

Time limit : 2 sMemory limit : 32 mb
Submitted : 155Accepted : 55

Problem Description

树是计算机中非常重要的非线性结构。对树本身的形态进行思考与研究,是一个 十分有趣且具有挑战性的过程。 我们对一个树的正式定义是:

1. 一个结点 x 组成的集 {x} 是一株树。 这个结点 x 也是这株树的根。
2. 假设 x 是一个结点, T1 ,T2 ,...,TK 是 K 株互不相交的树,我们可以构造一株新树:令 x 为根,并有 K 条边由 x 指向树 T1 ,T2 ,...,TK。这些边也叫做 分支,T1 ,T2 ,...,TK称作根为 x 的树的子树(subtree)。

——《数据结构》 大连理工大学出版社

如果在树的定义中,子树 T1 ,T2 ,...,TK 的相对顺序是重要的,那么这株树被称为有序树。

如果当两株树的差别仅仅在于子树的相对次序时,我们认为它们是同构的( 它们通过若干次子树交换可以变作和对方完全相同的树),我们称它们为有向树。

Input

输入包含一个非负整数序列。对于每个输入的N (1<=N<=200),求出 结点个数为N的有向树总数。输入以0结束。


Output

每个结果一行


Sample Input

1
2
0

Sample Output

1
1

Hint

Source