Placed in the N * N grid, N queen, require each line each column must have a queen, any two queens can not 45 Angle diagonal position in each other, each queen can see all of the other, please output placement scheme,

Input format: line of an integer, N, N=0
Output format: if there is a solution, from the first line to N the order of the line, output the queen's column number (starting from 1), a space between the column number, if there are multiple solutions, the output dictionary order minimum solution; If no solution, output "Impossible!!!!!! "; Each valid N output occupy a complete line,

Input the sample:
2
4
0

The output sample:
Impossible!!!!!!
4 1 2 3