High School Programming League 2011/12

Given a positive integer n, please find all sequences of positive integers x₁, x₂, ..., x_k such that the sum of all k elements of the above sequence is equal to n and for each i, 1<=i<k we have x_i+1-x_i in {-2, 0, 3}.

Input

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

Output

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.

Example

Input:
4
2
3
4
8

Output:
1 1 
2 

1 1 1 
3
 
1 1 1 1 
2 2 
3 1 
4 

1 1 1 1 1 1 1 1 
1 1 1 1 4 
1 1 4 2 
2 2 2 2 
3 1 1 1 1 1 
3 1 4 
3 3 1 1 
4 2 2 
4 4 
5 3 
8 

Scoring

By solving this problem you score 10 points.