#include<bits/stdc++.h>
using namespace std;
int n;
int a[21];
bool b[21];
int total=0;
bool pd(int x,int y);
void search(int t);
void print();
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        b[i]=true;
    search(1);
    cout<<"total:"<<total; 
}
void search(int t){
    for(int i=1;i<=n;i++){ 
        if(pd(a[t-1],i) && b[i]==true){
            a[t]=i;
            b[i]=false;
            if(t==n &&pd(a[1],a[n])){
                print();
            }   
            search(t+1);
            b[i]=true;
        }
    } 
     
}
 

bool pd(int x,int y){
    int n;
    bool f;
    if(x==0){
        return true;
    }
    f=true;
    n=x+y;
     
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){
            f=false;
            break;
        }
    }
    if(f==false || n==0 || n==1){
        return false;
    }
    else
    {
        return true;
    }
}
void print(){
    total=total+1;
    cout<<total<<":";
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
/**************************************************************
	Problem: 1358
	User: wangyichen2
	Language: C++
	Result: Accepted
	Time:11 ms
	Memory:2076 kb
****************************************************************/