#include <cstdio>

#include <iostream>

#include <cstring>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <algorithm>

using namespace std;

const int MAXN = ;

int emp[MAXN];  //emp[i] 表示从左往右 第 i 个皇后所在的行

int used[MAXN];  //标记这一行已经被使用

int n;

int cnt;    //合理的解的总数

int check(int key)  //判断第 key 个皇后的位置是否合理

{

    if(used[ emp[key] ])  //判断 行 是否合理

        return ;

    for(int i = ; i < key; i++) // 判断斜着是否和合理

        if( abs(i - key) == abs(emp[i] - emp[key]) )

            return ;

    return ;

}

void backtrack(int key)

{

    if(key > n) //满足条件的一个解

        cnt++;

    else

    {

        for(int i = ; i <= n; i++)  //第 key 列的皇后可以有放到 1 - N 行的N种选择（状态）

        {

            emp[key] = i;     //把第 key 个皇后放在第 i 行

            if(check( key )) //合法性

            {

                used[i] = ; //标记这 行 已被使用

                backtrack( key + ); // 继续求解下一个皇后

                used[i] = ; //恢复现场

            }

        }

    }

}

int main()

{

    //freopen("out.txt", "w", stdout);

    while(cin >> n)

    {

        cnt = ;

        memset(emp, , sizeof(emp));

        memset(used, , sizeof(used));

        backtrack();  //从第一个皇后开始放

    }

    return ;

}