#include <iostream>
#include<fstream>
using namespace std;
int total=0,i=0,v[14],ma[14][14];
bool ok=0;
int verificare(int n,int x, int y,int z)
{
    if((ma[x][y]==0 && z==1) || (ma[x][y]==1 && z==-1))
    {
        for(int a=0;a<n;a++)
        {
            if(z==1 || (z==-1 && ma[a][y]>=1))
            ma[a][y]+=z;
        }
        for(int w=1;w<=y && w<=x; w++)
        {
            if(z==1 || (z==-1 && ma[x-w][y-w]>=1))
            ma[x-w][y-w]+=z;
        }
           for(int w=1;w+y<n && w+x<n; w++)
        {
           if(z==1 || (z==-1 && ma[x+w][y+w]>=1))
            ma[x+w][y+w]+=z;
        }

        for(int w=1;w<=x && y+w<n; w++)
        {
            if(z==1 || (z==-1 && ma[x-w][y+w]>=1))
            ma[x-w][y+w]+=z;
        }
           for(int w=1;w<=y && w+x<n; w++)
        {
           if(z==1 || (z==-1 && ma[x+w][y-w]>=1))
            ma[x+w][y-w]+=z;
        }
        return 1;
    }
    else {
        return 0;
    }
}
int dame(int n, int i)
{
    int j,k;
    for(j=0;j<n;j++)
        {

                k=1;
                if(verificare(n,i,j,k)==1)
                {
                    if(ok==0)
                    {
                        v[i]=j+1;
                    }
                    if (i==n-1 && ok==0)
                    {
                        for(int x=0;x<=i;x++)
                        {
                            cout<<v[x]<<' ';
                        }
                    cout<<endl;
                    ok=1;
                    }
                    if(i==n-1)
                    {
                        total++;
                        k=-1;
                        verificare(n,i,j,k);
                    }
                    else{
                    dame(n,i+1);
                    k=-1;
                    verificare(n,i,j,k);
                    }
                }
        }
       if(i==0 && j==n)
    {
        return total;
    }

}
int main()
{
    ifstream cin("damesah.in");
    ofstream cout("damesah.out");
    int N;
    cin>>N;
    cout<<dame(N,i);
    return 0;
}