#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[20];  
bool v[20];  
bool add[20],s[50];  
int n,cnt,num;  
void dfs(int x){  
    if(x==n+1){  
        num++;  
        if(num<=3){  
           for(int i=1;i<n;i++) 
			   printf("%d ",a[i]);
		   printf("%d\n",a[n]);
		     
        }  
    }  
    for(int i=1;i<=n;i++){  
        if(!v[i]&&!add[x+i]&&!s[i-x+20]){  
          a[x]=i;  
		  v[i]=true;   
		  add[x+i]=true;  
		  s[i-x+20]=true;  
          dfs(x+1);  
          v[i]=false;   
		  add[x+i]=false;  
		  s[i-x+20]=false;  
        }  
    }  
}  
int main(){  
    //freopen("checker.in","r",stdin);  
    //freopen("checker.out","w",stdout);  
    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";  
        return 0;  
    }  
     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";  
        return 0;  
    }  
  
    dfs(1);  
    cout<<num;  
    return 0;  
  
}