#include<bits/stdc++.h>//再思考一下 
using namespace std;
int n;
int sum=0;
//int kk=0;
bool prime(int k){
    if(k==1) return 0;
    if(k==2) return 1;
    for(int i=2;i*i<=k;i++){
        //kk++;
        if(k%i==0){
            return 0;
        }
    }
    return 1;
}
int a[20];
bool flag[20];
void dfs(int k){
    if(k==n+1){
        bool flag1=0;
        for(int i=2;i<=n;i++){
            int cnt=a[i-1]+a[i];
            if(prime(cnt)==0){
                flag1=1;
                break;
            }
        }
        if(flag1==0){
            sum++;
            for(int i=1;i<=n;i++){
                printf("%d ",a[i]);
            }
            printf("\n");
        }
    }
   for(int i=1;i<=n;i++){//kk++;
       if(flag[i]==1){
           continue;
       }
       flag[i]=1;
       a[k]=i;
       dfs(k+1);
       flag[i]=0;
       a[k]=0;
   } 
}
int main(){
   freopen("dfs3.in","r",stdin);
   freopen("dfs3.out","w",stdout);
    scanf("%d",&n);
    dfs(1);
   printf("%d",sum);
  // cout<<kk;
    return 0;
}