Solution #3f414594-f572-42bb-a29b-50b5c75dc393

def solve(input):
    n = input["n"]
    
    def count_queens(n):
        if n in (2, 3):
            return 0
        
        factors = [0] * (n + 1)
        
        def sieve_of_eratosthenes():
            for start in range(2, n + 1):
                if factors[start] == 0: 
                    for multiple in range(start * start, n + 1, start):
                        factors[multiple] = start

        sieve_of_eratosthenes()

        primes = [index for index, factor in enumerate(factors) if factor == 0]
        
        def bitwise_combine(set1, set2):
            return set1 | set2
        
        dp = [0] * (1 << n)
        dp[0] = 1
        
        for col in range(n):
            for mask in range((1 << n) - 1, -1, -1):
                for p in primes:
                    bit = 1 << p
                    if (mask & bit) == 0:
                        new_mask = bitwise_combine(mask, bit)
                        dp[new_mask] += dp[mask]
        
        return dp[-1]

    return count_queens(n)