#include <iostream>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,nr,sol[200];
bool l[100],c[100],dp[200],ds[200];
void fil(int i, int j, int x)
{   l[i]=x;
    c[j]=x;
    dp[i-j]=x;
    ds[j+i]=x;
}
bool ver(int i, int j)
{   return l[i]==0&&c[j]==0&&dp[i-j]==0&&ds[j+i]==0;
}
void bkt(int k,int i, int j)
{   if(j==n+1)
    {   if(sol[i])
        {   j=1;
            i++;
        }
        else
        {  return;
        }
    }
    if(i==n+1)
    {   nr++;
        if(nr==1)
        {   for(int l=1;l<=n;l++) g<<sol[l]<<' ';
            g<<'\n';
        }
        return;
    }

    if(ver(i,j))
    {   fil(i,j,1);
        sol[i]=j;
        bkt(k+1,i,j+1);
        sol[i]=0;
        fil(i,j,0);
        bkt(k,i,j+1);
    }
    else bkt(k,i,j+1);

}
int main()
{
    f>>n;
    bkt(1,1,1);
    g<<nr;
    return 0;
}