#include<bits/stdc++.h>

using namespace std;

#define MAX 100 

int used1[MAX],used2[MAX],used3[MAX],n,ans=0,a[1000];//used1记录行的状态，used2记录（x，y）上面的斜线，used3记录下面的斜线 
void dfs(int x) //x表示第x行的皇后放在哪里 每行有且仅有一个皇后     
{
	if(x>n)//证明全部排满，输出解 
	{
		ans++;//排列个数 
		if(ans<=3)//输出前三个解，dfs函数保证了字典序 
		{
			for(int i=1;i<=n;i++)
			{
				cout<<a[i]<<' ';
			}
			cout<<endl;
		}
		return;//不return见祖宗 
	}
	for(int i=1;i<=n;i++)//枚举了所有的列 
	{
		if(used1[i]==0 && used2[x+i]==0 && used3[x-i+15]==0)//i判断列，x+i是上面的斜线，x-i是下面的，加15防止越界 
		{
			a[x]=i;//保存一遍结果 
			used1[i]=1,used2[x+i]=1,used3[x-i+15]=1;//记录不能放
			dfs(x+1);//搜索下一行 
			used1[i]=0,used2[x+i]=0,used3[x-i+15]=0;//回溯 
		}
	}
} 
int main()
{
	cin>>n;
	dfs(1);
	cout<<ans;
	return 0;	
}