#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int N,OK = false;
int SOL;
int C[20];
void BACKK( int );
void afisare();
void umplere();
int main()
{
    fin >> N;
    BACKK(1);
    fout<<SOL;
    return 0;
}
void BACKK(int k)
{
    if(k == N + 1)
    {
        if(OK == false)
            afisare();
        SOL ++;
        return;
    }
    for(int i = 1 ; i <= N ; ++i)
    {
        int ok , j;
        for(ok = true , j = 1; j < k && ok == true; ++j)
        {
            if(C[j] == i || (k - j) == abs(C[j] - i))
                ok = false;
        }
        if(ok)
        {
            C[k] = i;
            BACKK(k + 1);
        }
    }
}
void afisare()
{
    for(int i = 1 ; i <= N ; ++i)
        fout<< C[i] << ' ';
    fout<<'\n';
    OK = true;
}