N Queens Problem

This is the classic $$N$$ Queens problem. Given an integer $$N$$, place $$N$$ queens on an $$N \times N$$ chessboard such that no two queens threaten each other.

If a solution exists, print any one valid arrangement where each queen is denoted by 'Q' and empty cells by '.'. Otherwise, output No Solution.

inputFormat

The input consists of a single line containing a single integer $$N$$ representing the size of the chessboard.

outputFormat

If a valid arrangement exists, output the chessboard configuration with $$N$$ lines, each line containing $$N$$ characters (using 'Q' for a queen and '.' for an empty cell). If there is no solution, output exactly 'No Solution'.

sample

1

Q