N-Queens Problem

Given an integer N, place N queens on an N × N chessboard such that no two queens attack each other. Two queens attack each other if they share the same row, column, or diagonal. Formally, for any two queens placed at positions \((i, j)\) and \((k, l)\), they must satisfy:

\[ (i \neq k) \quad \text{and} \quad (j \neq l) \quad \text{and} \quad |i - k| \neq |j - l| \]

Your task is to print all distinct solutions. Each solution should be represented in a board layout format.

inputFormat

The input consists of a single integer N (1 ≤ N ≤ 10) on a single line, representing the size of the chessboard and the number of queens.

outputFormat

The output begins with an integer representing the number of valid solutions. For each solution, output N lines where each line is a string of length N containing exactly one 'Q' (representing a queen) and the remaining characters as '.' (empty spaces). Separate consecutive solutions with an empty line.

## sample

1

1
Q

</p>