POLSKI SPOJ

Napisz program wyznaczający wszystkie możliwe nierosnące ciągi składników (składniki mogą występować wielokrotnie) będących nieparzystymi liczbami naturalnymi, które w sumie dają zadaną liczbę n.

Input

W pierwszej linii liczba testów t. W każdym z kolejnych t wierszy znajduje się tylko jedna liczba 1 ≤ n ≤ 25.

Output

Dla każdego testu w oddzielnych liniach wszystkie możliwe ciągi nieparzstych liczb naturalnych, których elementy w sumie dają n. Ciągi powinny być podane w kolejności antyleksykograficznej, każdy ciąg w jednej linii.

Example

Input:
3
1
5
8

Output:
1 

5 
3 1 1 
1 1 1 1 1 

7 1
5 3
5 1 1 1
3 3 1 1
3 1 1 1 1 1
1 1 1 1 1 1 1 1