The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 1
Output: 1

Constraints:

• 1 ≤ n ≤ 9

Input format: A single integer n.

Output format: A single integer — the number of valid solutions.