#include <iostream>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int st[16], n, t;
void afisare ()
{
    for(int i=1; i<=n; i++)
        g<<st[i]<<" ";
    g<<'\n';
}
void bk (int k)
{
    int i;
    if(k>n)
    {
        t++;
        if(t==1)
            afisare();
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            st[k]=i;
            bool q=1;
            for(int j=1;j<k;j++)
                if(st[k]==st[j] || k-st[k]==j-st[j] || j+st[j]==k+st[k])
                {
                    q=0;
                    break;
                }
            if(q==1)
                bk(k+1);
        }
    }
}
int main()
{
    f>>n;
    bk(1);
    g<<t;
    return 0;
}