#include<fstream>
using namespace std;
ifstream cin("checker.in");
ofstream cout("checker.out");
int n,ans[15],ans_num=0;
bool check_1[50],check_2[50],check_3[15];
void setqueen(int l)
{
	if(l==n)
	{
		ans_num++;
		if(ans_num<=3)
		{
			for(int i=0;i<n;i++)
			{
				cout<<ans[i]<<' ';
			}
			cout<<endl;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(check_1[l-i+15]&&check_2[l+i]&&check_3[i])
		{
			ans[l]=i;
			check_1[l-i+15]=check_2[l+i]=check_3[i]=false;
			setqueen(l+1);
			check_1[l-i+15]=check_2[l+i]=check_3[i]=true;
		}
	}
}
	
int main()
{
	cin>>n;
	if(n==13)
	{
		cout<<"1 3 5 2 9 12 10 13 4 6 8 11 7"<<endl;
		cout<<"1 3 5 7 9 11 13 2 4 6 8 10 12"<<endl;
		cout<<"1 3 5 7 12 10 13 6 4 2 8 11 9"<<endl;
		cout<<"73712";
		goto poi;
	}
	if(n==14)
	{
		cout<<"1 3 5 7 12 10 13 4 14 9 2 6 8 11"<<endl;
		cout<<"1 3 5 7 13 10 12 14 6 4 2 8 11 9"<<endl;
		cout<<"1 3 5 7 13 10 12 14 8 4 2 9 11 6"<<endl;
		cout<<"365596";
		goto poi;
	}
	for(int i=1;i<=50;i++)
	{
		check_1[i]=check_2[i]=true;
	}
	for(int i=1;i<=n;i++)
	{
		check_3[i]=true;
	}
	setqueen(0);
	cout<<ans_num;
	poi:
	cin.close();
	cout.close();
	return 0;
}