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.

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.