#include <stdio.h>

#define maxn 20

int n,ans,s[maxn],hash[maxn],su[maxn*5];
FILE *f1,*f2;

void search(int x)
{
	int i,flag;
	if (x>=n)
	{
		ans++;
		for (i=0;i<n-1;i++)
			fprintf(f2,"%d ",s[i]);
		fprintf(f2,"%d\n",s[n-1]);
		return;
	}
	for (i=1;i<=n;i++)
	{
		if (hash[i]==0)
		{
			flag=0;
			if (x==0)
				flag=1;
			else
				if (su[s[x-1]+i])
					flag=1;
			if (flag)
			{	
				s[x]=i;
				hash[i]=1;
				search(x+1);
				hash[i]=0;
			}
		}
	}
}

void run(void)
{
	search(0);
}

void ini(void)
{
	int i,j;
	fscanf(f1,"%d",&n);
	for (i=3;i<=n*3;i++)
	{
		su[i]=1;
		for (j=2;j<i;j++)
			if (i%j==0)
			{
				su[i]=0;
				break;
			}
	}
		
}

int main(void)
{
	f1=fopen("dfs3.in","r");
	f2=fopen("dfs3.out","w");
	ini();
	if (n==1)
		ans=0;
	else
	run();
	fprintf(f2,"%d",ans);
	fclose(f1);fclose(f2);
	return 0;
}