#include <fstream>
using namespace std;

const int NMAX=13;
int sol[1+NMAX];
int tabla_sah[1+NMAX][1+NMAX];
int n,j,k,l;

int i_numar_sol=0;
bool prima_sol=1;

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

void blocare(int linie, int coloana)
{
    for(j=1;j<=n;j++)
    {
        tabla_sah[linie][j]=1;
        tabla_sah[j][coloana]=1;
        if(linie+j<=n && coloana+j<=n)
        {
            tabla_sah[linie+j][coloana+j]=1;
        }
        if(linie-j>=1 && coloana-j>=1)
        {
            tabla_sah[linie-j][coloana-j]=1;
        }
        if(linie+j<=n && coloana-j>=1)
        {
            tabla_sah[linie+j][coloana-j]=1;
        }
        if(linie-j>=1 && coloana+j<=n)
        {
            tabla_sah[linie-j][coloana+j]=1;
        }
    }
}

void track(int index)
{
    if(index>n)
    {
        if(prima_sol)
        {

            for(j=1;j<=n;j++)
            {
                out<<sol[j]<<' ';
            }
            out<<'\n';
            prima_sol=0;
        }
        i_numar_sol++;
    }
    else
    {
        int tabla_sah_curata[1+NMAX][1+NMAX];
        for(k=1;k<=n;k++)
        {
            for(l=1;l<=n;l++)
            {
                tabla_sah_curata[k][l]=tabla_sah[k][l];
            }
        }

        for(int i=1;i<=n;i++)
        {
            if(tabla_sah[index][i]==0)
            {
                blocare(index,i);
                sol[index]=i;
                track(index+1);
                for(k=1;k<=n;k++)
                {
                    for(l=1;l<=n;l++)
                    {
                        tabla_sah[k][l]=tabla_sah_curata[k][l];
                    }
                }
            }
        }
    }
}

int main()
{

    in>>n;

    track(1);

    out<<i_numar_sol;

    return 0;
}