Place n queens on an n × n chessboard so that no two queens attack each other: no two may share a row, a column or a diagonal.
Given n, return the number of distinct ways to do it.
Examples
Example 1
- Input
- n = 4
- Output
- 2
Example 2
- Input
- n = 1
- Output
- 1
Constraints
1 <= n <= 9