#include <bits/stdc++.h>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");

int st[15],n,k;
bool ok=1;

int abs(int a,int b)
{
    if(a>b)
        return a-b;
    return b-a;
}

int solutie(int p)
{
    return p==n;
}

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

void afis()
{
    if(ok==1)
    {
        for(int i=1;i<=n;++i)
            g<<st[i]<<" ";
        g<<"\n";
    }
    k+=2;
}

void bk(int p)
{
    int x;
    if(p==1)
        x=n/2+n%2;
    else
        x=n;
    for(int i=1;i<=x;++i)
    {
        st[p]=i;
        if(verifica(p))
            if(solutie(p))
            {
                afis();
                ok=0;
            }
        else
            bk(p+1);
    }
}

int main()
{
    f>>n;
    bk(1);
    g<<k<<"\n";
    return 0;
}