Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS11SEQ - Sequences

Given a positive integer n, please find all sequences of positive integers x1, x2, ..., xk 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 xi+1-xi 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.


Added by:kuszi
Date:2012-01-15
Time limit:1s-1.875s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 CLOJURE PERL6
Resource:High School Programming League

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.