High School Programming League Problems Archive

Given a natural number n, please find all non-decreasing sequences of integers, such that the sum of all the elements of the sequence is equal to n. Numbers in the sequence may repeat. Due to the imposed politically correct "parity policy" each valid sequence must contain the same number of odd and even elements.

Input data specification

The first line contains the number of test cases t. Each of the following t lines contains just one number 1 <= n <= 40.

Output data specification

For each test case print all possible sequences satisfying the problem criteria. Sequences must be given in the lexicographic order, with each sequence printed in a separate line.

If no valid sequence exists for a given value of n, print the text "Impossible".

Example 1

Input:
3
4
8
7

Output:
Impossible
1 1 2 4
1 2 2 3
1 6
2 5
3 4

Scoring

By solving this problem you will score 10 points.