Shortening codes

Input

The input consist of unknown number of tests. Each test is a line with one integer x (0<=x<25). The input ends with x=0 (for which You shouldn't print anything).

Output

For each test You should print all possible non-decreasing sequences of integers (which may occur more than one time) which totalled equal x. In each sequence the i-th number should be greater than, or equal to, the preceding number. The sequences themselves should also be sorted into numerically ascending order.

Example

Input:
1
2
3
4
5
0

Output:
1
1 1
2
1 1 1
1 2
3
1 1 1 1
1 1 2
1 3
2 2
4
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

Special thanks to Łukasz Kuszner for the concept of this task.