N Queens - placement

Input

The size of the chess board $n$ (1 \le n \le 10).

Output

If it is possible to place all the $n$ queens in such a way that no queen attacks another queen, then print $n$ lines having $n$ integers. The integer in $i$-th line and $j$-th column will denote the cell $(i,j)$ of the board and should be $1$ if a queen is placed at $(i,j)$ and $0$ otherwise. If there is more than one way of placing queens print any of them. If it is not possible to place all $n$ queens in the desired way, then print "Not possible" (without quotes).

Examples