#include <iostream>
#include <fstream>
#define MAXN 14
#define INFILE "damesah.in"
#define OUTFILE "damesah.out"
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
int n,v[MAXN],kk;
bool d1[MAXN*2],d2[MAXN*2],c[MAXN],ok;
void afis()
{
    if(!ok)
    {
        ok=1;
        for(int i=1;i<=n;i++)g<<v[i]<<" ";
        g<<'\n';
    }
    kk++;
}
void bkt(int k)
{
    for(int i=1;i<=n;i++)
        if((!c[i])&&(!d1[n+k-i])&&(!d2[i+k]))
        {
            c[i]=d1[n+k-i]=d2[i+k]=1;
            v[k]=i;
            if(k==n)afis();
            else bkt(k+1);
            c[i]=d1[n+k-i]=d2[i+k]=0;
        }
}
int main()
{
    f>>n;
    bkt(1);
    g<<kk;
    f.close();
    g.close();
    return 0;
}