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.
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.
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.
8 0
5 3 1 6 8 2 4 7