Description

Little Joan has N blocks,all of them of different sizes. He is playing to build cities in the beach. A city is just a collection of buildings.

A single block over the sand can be considered as a building. Then he can construct higher buildings by putting a block above any other block. At most one block can be put immediately above any other block. However he can stack several blocks together to construct a building. However, it’s not allowed to put bigger blocks on top of smaller ones, since the stack of blocks may fall. A block can be specified by a natural number that represents its size.

It doesn’t matter the order among buildings. That is:

1 3
2 4

3 1
4 2

Your problem is to compute the number of possible different cities using N blocks. We say that #(N) gives the number of different cities of size N. If N=2, for instance, there are only two possible cities:

City #1:
1 2

In this city both blocks of size 1 and 2 are put over the sand.

City #2:
1
2

In this city block of size 1 is over block is size 2, and block of size 2 is over the sand.

So, #(2)=2.

Input

A sequence of non-negative integer numbers, each of one in different line. All of them but the last one are natural numbers. The last one is 0 and means the end. Each natural number is less than 900.

Output

For each natural number I in the input, you must write a line with the pair of numbers I, #(I).

2
3
0

2, 2
3, 5

Problemsetter: Dr. Mauricio Javier Osorio Galindo