#include<iostream>
#include<cmath>
using namespace std;
int n;
int a[21];//用于存放素数环数字
bool b[21];//用其下标代表素数环中的数字，其存放内容代表改数字是否可用
int total=0;//代表素数环个数

bool pd(int x,int y);//判断x+y是否为素数
void search(int t);//第归判断1-n是否满足条件
void print();//打印满足条件的素数环

int main(){
    cin>>n;
	for(int i=1;i<=n;i++)
		b[i]=true;
		
	//a[0]=1;//保证a[1]的第一位可以放1 

	//从1开始搜索
	search(1);

	//打印出素数环个数
	cout<<"total:"<<total; 
	
}

//第归判断1-n是否满足条件
//这里的ｔ代表素数环中第几个
void search(int t){
	
	//遍历1-n个数字
	for(int i=1;i<=n;i++){
		//如果第ｉ个数字与他上一个数字（放入环中的数字）相加是素数i+a[t-1]
		//并且该数字没有使用过ｂ[i]=true 
		if(pd(a[t-1],i) && b[i]==true){
			a[t]=i;//存放进素数环
			b[i]=false;//标记该数已经被使用过了
			//n个数全部遍历结算
			if(t==n &&pd(a[1],a[n])){
				//判断头尾相加是否是素数
				//打印素数环
				print();
			}	
			search(t+1);//查找下一个
			b[i]=true;//不满足条件的情况下把这个ｉ给放出来
		}
	} 
	
}

//判断x+y是否为素数
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;//跳出循环
		}
	}
	
	//0,1 不是素数，2是素数
	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: admin
	Language: C++
	Result: Accepted
	Time:9 ms
	Memory:2076 kb
****************************************************************/