#include<iostream>
#include<cstdio>  
using namespace std;  
    int ans[20];  
    bool lala[20];  
    bool bibi[20],zizi[50];  
    int n,cnt,num;  
    void biu(int x){  
        if(x==n+1){  
            num++;  
            if(num<=3){  
               for(int i=1;i<n;i++)  printf("%d ",ans[i]);  
               printf("%d\n",ans[n]);  
            }  
        }  
        for(int i=1;i<=n;i++){  
            if(!lala[i]&&!bibi[x+i]&&!zizi[i-x+20]){  
              ans[x]=i;  lala[i]=true;   bibi[x+i]=true;  zizi[i-x+20]=true;  
              biu(x+1);  
              lala[i]=false;   bibi[x+i]=false;  zizi[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;  
        }  
      
        biu(1);  
        printf("%d\n",num);  
        return 0;  
      
    }