#include <iostream>
#include <fstream>

using namespace std;

int N,ct=0;

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

int s[50],v1[50],v2[50],v[50];

void bktr(int n)
{
    if(n>N)
    {
        if(!ct)
        {
            for(int i=1;i<=N;i=i+1)
                if(v[i])
                    g<<v[i]<<" ";
                    g<<"\n";
                    ct++;
        }
        else ct++;
    }
    for(int i=1;i<=N;i=i+1)
        if(s[i]==0 && v1[i+n]==0 && v2[i-n+N+1]==0)
            {
                v[n]=i;
                s[i]=1;
                v1[i+n]=1;
                v2[i-n+N+1]=1;
                bktr(n+1);
                s[i]=0;
                v1[i+n]=0;
                v2[i-n+N+1]=0;
            }
}

int main()
{
    f>>N;
    bktr(1);
    g<<ct;
    return 0;
}