Description
The eight queens puzzle is the problem of putting eight chess queens on an 8 × 8 chessboard such that none of them is able to capture any other. The puzzle has been generalized to arbitrary n × n boards. Given n, you are to find a solution to the n queens puzzle.
Input
The input contains multiple test cases. Each test case consists of a single integer n between 8 and 300 (inclusive). A zero indicates the end of input.
Output
For each test case, output your solution on one line. The solution is a permutation of {1, 2, …, n}. The number in the ith place means the ith-column queen in placed in the row with that number.
Sample Input
8
0
Sample Output
5 3 1 6 8 2 4 7