#include<iostream>
#include<cstring>
#include<fstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<iomanip>
using namespace std;
fstream fin("damesah.in",ios::in),fout("damesah.out",ios::out);
int n,gm[15][15],linie[15],p=0,coloana[15],diag1[15],diag2[15],drumj[15];
void scrie(int k)
{
    int i;
    if(p==0)
    {
        for(i=1;i<k;i++)
        {
            fout<<drumj[i]<<" ";
        }
        fout<<"\n";
        p=1;
    }
    else
    {
        p++;
    }
    return ;
}
void back(int k)
{
    int i,l,c,d1,d2;
    if(k==n+1)
    {
        scrie(k);
        return;
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            d1=n-k+i;
            d2=k+i-1;
            if(diag1[d1]==0&&diag2[d2]==0&&coloana[i]==0)
            {
                diag1[d1]=diag2[d2]=coloana[i]=1;
                drumj[k]=i;
                back(k+1);
                diag1[d1]=diag2[d2]=coloana[i]=0;
            }
        }
    }
    return ;
}
int main()
{
    fin>>n;
    back(1);
    fout<<p<<"\n";
    fout.close();
    fin.close();
    return 0;
}