Queens (2) P17921

Write a program to print all the ways to place n queens on an n × 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 × 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.