Various sums

Find all nondecreasing sequences of positive numbers which sum to a given number.

Input

In the first line there will be a number of data sets t. In the next t lines data sets follows. Each data set is a single number n_i.

Output

For each data set write all nondecreasing sequences of positive numbers which sum to n_i. Sequences should be ordered in a lexicographical order and separated by new lines.

Example

Input:
2
1
5

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