#include<iostream>
#include<fstream>
#include<algorithm>
#include<bitset>
#include<math.h>
using namespace std;
bool b;
int cont;
int v[20];
ofstream so("damesah.out");
void afis(int n)
{
    int i;
    for(i=0;i<n;++i)
        so<<v[i]+1<<' ';
    b=true;
}
void dame(int n,int k)
{
    if(k==n)
    {
        if(!b)
            afis(n);
        ++cont;
    }
    else
    {
        int i,j;
        for(i=0;i<n;++i)
        {
            for(j=0;j<k;++j)
            {
                if(v[j]==i||abs(v[j]-i)==k-j)
                    break;
            }
            if(j==k)
            {
                v[k]=i;
                dame(n,k+1);
            }
        }
    }
}
int main()
{
    ifstream si;
    si.open("damesah.in");

    int n;
    si>>n;
    dame(n,0);
    so<<'\n'<<cont<<'\n';
}