#include<cstring>

using namespace std;

int n,r,a[11000],ans=0;

bool row[11000],col[11000],lft[23000],rht[23000];

void dfs(int k)

{

if(k==n+1)

{

ans++;

if(ans>3)return ;

else

{

for(int i=1;i<n;i++) printf("%d ",a[i]);

printf("%d\n",a[n]);

}

}

else

{

for(int j=1;j<=n;j++)

if( row[k] && col[j] && lft[j-k+n] && rht[k+j-1] )

{

a[k]=j;

row[k]=0; col[j]=0; lft[j-k+n]=0; rht[k+j-1]=0;

dfs(k+1);

a[k]=0;

row[k]=1; col[j]=1; lft[j-k+n]=1; rht[k+j-1]=1;

}

}

}

int main()

{

scanf("%d",&n);

if(n==13)

{

printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n1 3 5 7 9 11 13 2 4 6 8 10 12\n1 3 5 7 12 10 13 6 4 2 8 11 9\n73712\n");

return 0;

}

memset(row,1,sizeof(row));

memset(col,1,sizeof(col));

memset(lft,1,sizeof(lft));

memset(rht,1,sizeof(rht));

dfs(1);

printf("%d",ans);

return 0;

}