#include<bits/stdc++.h>
using namespace std;
int a[3000][3000],b[3000][3000];
int n,m;
int cnt;
int fa[20],fb[20],fc[20];
void dfs(int h)
{
	 if(h>n)
	 {
	 	cnt++;
	 	for(int i=1;i<=n;i++)
	 	{
	 		for(int j=1;j<=n;j++)
	 		{
	 			if(a[i][j]==1)
	 			{
	 			   b[i][cnt]=j;
				}
			}
		}
		return ;
	 }
	 for(int j=1;j<=n;j++)
	 {
	 	 if(fa[j]==0&&fb[h+j]==0&&fc[h-j+n]==0)
	 	 {
	 	 	a[h][j]=1;
	 	 	fa[j]=fb[h+j]=fc[h-j+n]=1;
	 	 	dfs(h+1);
	 	 	a[h][j]=0;
	 	 	fa[j]=fb[h+j]=fc[h-j+n]=0;
		 }
	 }
} 
int main(){
	cin>>n;
	dfs(1);
    for(int i=1;i<=cnt;i++) 
    {
    	  for(int j=1;j<=n;j++)
    	  {
    	  	  cout<<b[j][i]<<" ";
		  }
		  cout<<endl;
	}
	cout<<cnt;
    return 0;
}