Queens (2) P17921

Write a program to print all the ways to place $n$ queens on an $n \times n$ chessboard so that no queen threatens another queen.

Input

Input consists of a natural number $n > 0$.

Output

Print all the ways to put $n$ queens on an $n \times n$ chessboard so that no queen threatens another queen. The queens must be marked with a ‘Q’, and the empty positions with a dot. Print an empty line after each board.

Information about the checker

You can print the solutions to this exercise in any order.