Napisz program wyznaczający wszystkie możliwe niemalejące ciągi składników naturalnych (składniki mogą występować wielokrotnie), 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 ≤ 20 .

Output

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

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