#include<cstdio>
#include<iostream>
using namespace std;
int n,ans=0,a[20]={0},b[20]={0};
void print()
{
	ans++;
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}
bool sushu(int d)
{
	for(int i=2;i*i<=d;i++)
	if(d%i==0)return 0;
	else return 1;
}
void search(int i,int n)
{
	for(int j=1;j<=n;j++)if((!b[j])&&sushu(j+a[i-1]))
    {
	  	a[i]=j;
	  	b[j]=1;
		if(i==n)print();
		else search(i+1,n);
		b[j]=0;
	}
}
int main()
{
	freopen("dfs3.in","r",stdin);
	freopen("dfs3.out","w",stdout);
	scanf("%d",&n);
	search(1,n);
	printf("%d",ans);
	return 0;
}