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

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

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.

3
4

{ 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 }