ch0405-9276 Connected Graph

描述

An undirected graph is a set V of vertices and a set of E∈{V*V} edges.An undirected graph is connected if and only if for every pair (u,v) of vertices,u is reachable from v. You are to write a program that tries to calculate the number of different connected undirected graph with n vertices. For example,there are 4 different connected undirected graphs with 3 vertices.

输入

The input contains several test cases. Each test case contains an integer n, denoting the number of vertices. You may assume that 1<=n<=50. The last test case is followed by one zero.

输出

For each test case output the answer on a single line.

样例输入

1
2
3
4
51
2
3
4
0

样例输出

1
2
3
41
1
4
38

限制

• 时间限制：1000ms
• 内存限制：128MB