# Solution to the <i>n</i> Queens Puzzle

Time Limit: 1000MS

Memory Limit: 131072K

## 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

N/A