bool clash(int c1,int l1,int r1,int c2,int l2,int r2){

    if(c1&c2)return false;

    if(l1&l2)return false;

    if(r1&r2)return false;

    return true;

}

int ans;

void dfs(int step,int n,int c1,int l1,int r1){

    if(step == n){

        ans++;

        return ;

    }

    for(int i = 0 ; i < n ; i ++){

        int c2 = 1 << i;

        int l2 = 1 << (n-step+i);

        int r2 = 1 << (i+step);

        if(clash(c1,l1,r1,c2,l2,r2)){

            dfs(step+1,n,c1|c2,l1|l2,r1|r2);

        }

    }

}

int totalNQueens(int n) {

   

    ans = 0;

    dfs(0,n,0,0,0);

    return ans;

}