#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<deque>
#define itn int
using namespace std;
int n,a[20];bool visit[20];int ans=0;
inline bool is_prime(int n){
	if (n==1||n==0) return false;
	if (n==2) return true;
	int temp=sqrt(n);
	for (int i=2;i<=temp;i++){
		if (n%i==0) return false;
	}
	return true;
} 
inline void readln(){
	freopen("dfs3.in","r",stdin);
	freopen("dfs3.out","w",stdout);
	scanf("%d",&n);
}
inline void print(){
	for (int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	cout<<endl;
}
inline void dfs(int step){
	if (step==n+1) {print();ans++;return;}
	for (int i=1;i<=n;i++){
		if (visit[i]==false)
		  if (is_prime(i+a[step-1])){
			a[step]=i;
			visit[i]=true;
			dfs(step+1);
			visit[i]=false;
		}
	}
}
int Main(){
	readln();
	memset(visit,0,sizeof(visit));
	for (int i=1;i<=n;i++){
			a[1]=i;
			visit[i]=true;
			dfs(2);
			visit[i]=false;
	}
	printf("%d",ans); 
	return 0;
}
int main(){;}
int xlm=Main();