#include<cstdio>  
    using namespace std;  
    int ans[20];  
    bool vis[20];  
    bool add[20],sub[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 ",ans[i]);  
               printf("%d\n",ans[n]);  
            }  
        }  
        for(int i=1;i<=n;i++){  
            if(!vis[i]&&!add[x+i]&&!sub[i-x+20]){  
              ans[x]=i;  vis[i]=true;   add[x+i]=true;  sub[i-x+20]=true;  
              dfs(x+1);  
              vis[i]=false;   add[x+i]=false;  sub[i-x+20]=false;  
            }  
        }  
    }  
    int main(){  
        freopen("checker.in","r",stdin);  
        freopen("checker.out","w",stdout);  
        scanf("%d",&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;  
        }  
      
        dfs(1);  
        printf("%d\n",num);  
        return 0;  
      
    }