===== Prelude 1 to Backtracking -- Permutations ======

For this prelude, you are to set up a skeleton file for doing backtracking and use it to compute permutations of N.

===== Input =====

Input consists of a sequence of non-negative integers, N (0 < N < 10), one per line.  

===== Output =====

For each input value, N, generate the permutations of 1..N.  Each permutation should be on a line by itself, surrounded by { }, in lexicographic order (see sample output).  A single blank line should separate each test case.

===== Sample Input =====

<code>
3
4
</code>

===== Sample Output =====

<code>
{ 1 2 3 }
{ 1 3 2 }
{ 2 1 3 }
{ 2 3 1 }
{ 3 1 2 }
{ 3 2 1 }

{ 1 2 3 4 }
{ 1 2 4 3 }
{ 1 3 2 4 }
{ 1 3 4 2 }
{ 1 4 2 3 }
{ 1 4 3 2 }
{ 2 1 3 4 }
{ 2 1 4 3 }
{ 2 3 1 4 }
{ 2 3 4 1 }
{ 2 4 1 3 }
{ 2 4 3 1 }
{ 3 1 2 4 }
{ 3 1 4 2 }
{ 3 2 1 4 }
{ 3 2 4 1 }
{ 3 4 1 2 }
{ 3 4 2 1 }
{ 4 1 2 3 }
{ 4 1 3 2 }
{ 4 2 1 3 }
{ 4 2 3 1 }
{ 4 3 1 2 }
{ 4 3 2 1 }
</code>