#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
using namespace std;
int n,a[30],mp[30],zx[100],yx[100],num=0;//a[]表示某列被占领，mp存放输出数据，,zy,zx分别判断斜方向能否被打倒 
void print()
{
	if(num<=3)
	{
		for(int i=1;i<=n;i++)
		{
			cout<<mp[i]<<" ";		
		}
		cout<<endl;
	}
}
void search(int k)
{	
	if(k>n) 
	{
		num++;
		print();
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if((a[i]==0)&&(zx[i+k]==0)&&(yx[k-i+n]==0))
		{
			mp[k]=i;//存放输出数组 
			a[i]=1;//第i列被战领 
			zx[i+k]=1;//两条对角线 
			yx[k-i+n]=1;
			
			search(k+1);
			
			a[k]=0;
			zx[i+k]=0;
			yx[k-i+n]=0; 
			
		}
		
	}
} 
int main()
{
	cin>>n;
	search(1);
	cout<<num;
	return 0;
}