#include <iostream>
#include <fstream>
using namespace std;

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

int sol[100], vizc[50], vizds[50], vizdp[50],n, nr=0;

void afisare()
{
    for (int i=0; i<n; i++)
        g << sol[i]+1 <<' ';
    g << endl;
}

void backt(int k)
{
    if (k==n)
    {
        if(nr==0)
            afisare();
        nr++;
        return;
    }
    for (int v=0; v<n; v++)
    {
        if (vizc[v]==0 && vizdp[k-v+n]==0 && vizds[k+v]==0)
        {
            sol[k]=v;
            vizc[v]=1;
            vizdp[k-v+n]=1;
            vizds[k+v]=1;
            backt(k+1);
            vizc[v]=0;
            vizdp[k-v+n]=0;
            vizds[k+v]=0;
        }
    }
}

int main()
{
    f >> n;
    backt(0);
    g << nr;
    return 0;
}