#include<iostream>
#include<cstring>
#include<fstream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<iomanip>
using namespace std;
fstream fin("damesah.in",ios::in),fout("damesah.out");
int n,m[15][15],bif[15][15],gm[15][15],p=0,di[]={-1,-1,0,1,1,1,0,-1},dj[]={0,1,1,1,0,-1,-1,-1},ok,t[1000][15];
int drumj[15],a[15],indice[15];
void scrie()
{
    int i,k=1,i1,j1,aux;
    memcpy(a,indice,n*sizeof(int));
    sort(a,a+n);
    if(p==0)
    {
        for(i=0;i<n;i++)
        {
            aux=a[i];
            j1=aux%n;
            aux-=j1;
            i1=aux/n+1;
            bif[i1][j1]=1;
        }
        for(i=0;i<n;i++)
        {
            fout<<drumj[i]<<" ";
        }
        fout<<"\n";
        p=1;
        memcpy(t[p],a,n*sizeof(int));
    }
    else
    {
        for(i=0;i<n;i++)
        {
            aux=a[i];
            j1=aux%n;
            aux-=j1;
            i1=aux/n+1;
            bif[i1][j1]=1;
        }
        for(i=1;i<=p;i++)
        {
            if(memcmp(t[i],a,n*sizeof(int))==0)//daca se gaseste a in t
            {
                k=0;
                break;
            }
        }
        if(k==1)
        {
            memcpy(t[++p],a,n*sizeof(int));
        }
    }
}
void ceva(int g,int i,int j,int dir=-1)
{
    int k;
    if(gm[i][j]==1)
    {
        ok=0;
    }
    if(i>n||i<1||j>n||j<1)
    {
        return;
    }
    m[i][j]+=g;
    if(dir!=-1)
    {
        ceva(g,i+di[dir],j+dj[dir],dir);
    }
    else
    {
        for(k=0;k<8;k++)
        {
            ceva(g,i+di[k],j+dj[k],k);
        }
    }
}
void back(int k)
{
    int i,j;
    if(k==n)
    {
        scrie();
        return;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(m[i][j]==0&&gm[i][j]==0&&bif[i][j]==0)
            {
                ok=1;
                ceva(1,i,j);
                m[i][j]=0;
                if(ok==0)
                {
                    ceva(-1,i,j);
                    m[i][j]=0;
                }
                else
                {
                    gm[i][j]=1;
                    drumj[k]=j;
                    indice[k]=i*n-n+j;
                    back(k+1);
                    ceva(-1,i,j);
                    m[i][j]=0;
                    gm[i][j]=0;
                }
            }
        }
    }
}
int main()
{
    fin>>n;
    back(0);
    fout<<p<<"\n";
    fout.close();
    fin.close();
    return 0;
}