#include <iostream>
#include <cmath>
#include <fstream>

using namespace std;

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

int st[125],n;

void tipar(int p)
{
    for(int i=1;i<=p;i++)
        g<<st[i]<<' ';
    g<<'\n';
}

int val(int p)
{
    for(int i=1;i<p;i++)
        if(st[i]==st[p] || p-i==abs(st[p]-st[i]))
            return 0;
    return 1;
}

void bktr(int p,int &prim,int &nr)
{
    for(int x=1;x<=n;x++)
    {
        st[p]=x;
        if(val(p))
        {
            if(p==n)
                {
                    if(prim==0)
                    {
                        prim=1;
                        tipar(p);
                    }
                    nr++;
                }
            else
                bktr(p+1,prim,nr);
        }
    }
}

int main()
{
    f>>n;
    int nr=0,prim=0;
    bktr(1,prim,nr);
    g<<nr;
}