#include <bits/stdc++.h>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,nr[15],af;
void backtr(int x);
void afis();
int test(int x);
int main()
{
    f>>n;
    backtr(1);
    g<<'\n'<<af;
    g.close();
    return 0;
}
int test(int x)
{
    for(int i=1;i<x;i++)
        if(abs(nr[i]-nr[x])==abs(i-x) || nr[x]==nr[i])
            return 0;
    if(x==nr[x])return 0;
    return 1;
}
void backtr(int x)
{
   for(int i=1;i<=n;i++)
   {
       nr[x]=i;
       if(test(x))
       {
           if(x==n&&!af){afis();}
           if(x==n)af++;
           else backtr(x+1);
       }

   }
}
void afis()
{
   for(int i=1;i<=n;i++)
       g<<nr[i]<<' ';
}