#include <fstream>
#include <iostream>
#include <math.h>

using namespace std;
int n,a[30],nrsol,vv=1;
ifstream in ("damesah.in");
ofstream out ("damesah.out");

void afis()
{
    int i,j;

    for(i=0;i<n;i++)
    {out<<a[i]+1<<" ";

    }
    out<<'\n';
}

void reg(int l)
{int i,j,ok;

    if(n==l){ ++nrsol;if (vv) afis(),vv=0;}
        else
        for(i=0;i<n;i++){
            for(ok=1,j=0;j<l;j++)
            if(a[j]==i||abs(a[j]-i)==(l-j)) ok=0;
           if(ok) {a[l]=i; reg(l+1);}
           }

}
int main()
{int h;
in>>n;
reg(0);
out<<nrsol<<'\n';
    return 0;


}