描述

无向图由顶点集$V$和边集$E$（$E$是$V$与$V$的笛卡尔积的子集）组成。当且仅当对于任意顶点对($u$, $v$) ，$u$可从$v$到达时，该无向图是连通的。

你要编写一个程序，计算具有$n$个顶点的不同连通无向图的数量。例如，$3$个顶点的不同连通无向图有$4$个。

输入

输入包含若干测试用例。每个测试用例包含一个整数$n$，表示顶点数量。可假设$1 \leq n \leq 50$。最后一个测试用例后跟着一个$0$。

输出

对于每个测试用例，在单独一行输出答案。

输入数据1

1
2
3
4
0

输出数据1

1
1
4
38

来源

LouTiancheng@POJ