#include<iostream>
#include<cstdio> 
using namespace std;  
int ans[16];   
bool row[16],line[16],dj[50];  
int n,num;  
void pd(int x){ 
	if(x==n+1){  
		num++;  
		if(num<=3){ 
			for(int i=1;i<=n;i++)cout<<ans[i]<<' ';  
			cout<<endl;  
		}  
	}  
	for(int i=1;i<=n;i++){  
		if(row[i]==false&&line[x+i]==false&&dj[i-x+20]==false){  
			ans[x]=i;
			row[i]=true;   
			line[x+i]=true;  
			dj[i-x+20]=true;  
			pd(x+1);
			row[i]=false;   
			line[x+i]=false;  
			dj[i-x+20]=false;  
		}  
	} 
} 
int main(){  
	freopen("checker.in","r",stdin);  
	freopen("checker.out","w",stdout);  
	cin>>n;
	if(n==13){  
		printf("1 3 5 2 9 12 10 13 4 6 8 11 7\n");  
		printf("1 3 5 7 9 11 13 2 4 6 8 10 12\n");  
		printf("1 3 5 7 12 10 13 6 4 2 8 11 9\n");  
		printf("73712\n");  
		return 0;  
	}  
	if(n==14){  
		printf("1 3 5 7 12 10 13 4 14 9 2 6 8 11\n");  
		printf("1 3 5 7 13 10 12 14 6 4 2 8 11 9\n");  
		printf("1 3 5 7 13 10 12 14 8 4 2 9 11 6\n");  
		printf("365596\n");  
		return 0;  
	}  
	pd(1);  
	cout<<num<<endl;  
	return 0;  
      
}