N-Queens Count

Problem

Count the number of distinct placements of N queens on an N×N chessboard so none attacks another.

Input

Single integer N.

Output

The count of valid placements.

Constraints

1 ≤ N ≤ 13

Sample input

Sample output

Explanation

Two valid arrangements for 4×4.

backtrackingrecursion@Google@Microsoft

Visible test cases

in: 4

out: 2

in: 8

out: 92

Your solution — run it, use AI if stuck