Sequences of Removed Stones

You are given a positive integer \(n\) representing the number of stones, numbered from 1 to \(n\). Your task is to generate all possible sequences in which the stones can be removed. Each sequence is a permutation of the numbers from 1 to \(n\), and the sequences must be listed in lexicographical order.

The input contains several test cases. For each test case, the integer \(n\) is provided on a separate line. The input terminates when \(n = 0\), which should not be processed.

For each test case, output all the permutations (sequences) on separate lines. Separate the output of consecutive test cases with an empty line.

inputFormat

The input is provided via standard input (stdin). It consists of several lines, each containing a single integer \(n\) where \(1 \le n \le 9\). Input ends with a line containing a single 0, which should not be processed.

outputFormat

For each test case, output all lexicographically sorted permutations of the numbers from 1 to \(n\). Each permutation should be printed on a separate line with the numbers separated by a single space. Separate outputs of consecutive test cases with an empty line. The output should be printed to standard output (stdout).

1
0

1