Cool permutations P51435

Statement

thehtml

In this problem, we will say that a permutation is cool is it does not have two adjacent consecutive numbers. Given n, print all the cool permutations of {0, …, n − 1}.

Input

input consists of several cases, each with an n between 1 and 9.

Output

For every case, print in lexicographical order all the cool permutations of {0, …, n − 1}. Print a line with 20 asterisks at the end of every case.

Public test cases

Input

Output

0
********************
********************
********************
1 3 0 2
2 0 3 1
********************
0 2 4 1 3
0 3 1 4 2
1 3 0 2 4
1 3 0 4 2
1 4 2 0 3
2 0 3 1 4
2 0 4 1 3
2 4 0 3 1
2 4 1 3 0
3 0 2 4 1
3 1 4 0 2
3 1 4 2 0
4 1 3 0 2
4 2 0 3 1
********************

Information

Author: Salvador Roura
Language: English
Translator: Salvador Roura
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++ Python