#include <fstream>
#include <cmath>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,nrsol,c[30],gasit;
void reg(int);
int main()
{
    f>>n;
    reg(0);
    g<<nrsol;
    f.close();g.close();
    return 0;
}
void reg(int k)
{
    int i,j,ok;
    if(k==n)
        {
            nrsol++;
            if(nrsol==1)
                {for(i=0;i<n;i++)
                    {gasit=0;
                        for(j=0;j<n && !gasit;j++)
                        if(j==c[i]) g<<j+1<<" ",gasit=1;}
                g<<'\n';}
        }
    else
        for(i=0;i<n;i++)
        {
            for(ok=1,j=0;j<k;j++)
                if(c[j]==i || abs(c[j]-i)==(k-j)) ok=0;
            if(ok)
            {
                c[k]=i;
                reg(k+1);
            }
        }
}