#include <bits/stdc++.h>

using namespace std;

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

int n,NrSol,c[15];
bool primsol=true;

void Afisare()
{
    int i,j;
    if(primsol)
    {
        for(i=0; i<n; i++)
            fout << c[i] << " ";
        fout << '\n';
        primsol=false;
    }
}

void Plaseaza_Regina(int k)
{
    int i,j,ok;
    if(k==n)
        Afisare(), NrSol++;
    else
    for(i=1;i<=n;i++)
    {
        for(ok=1, j=0; j<k; j++)
            if(c[j]==i || abs(c[j]-i)==(k-j))
                ok=0;
        if(ok)
        {
            c[k]=i;
            Plaseaza_Regina(k+1);
        }
    }
}

int main()
{
    fin >> n;
    Plaseaza_Regina(0);
    fout << NrSol;
    return 0;
}