#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 15+5;
FILE *fin, *fout;
const int pri[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
bool vis[maxn];
int ans = 0, n, d[maxn];
void print_d() {
	for(int i = 1; i <= n; i++)
		fprintf(fout, "%d ", d[i]);
}
bool check(int a) {
	int p = lower_bound(pri, pri+15, a)-pri;
	if(pri[p] == a) return true;
	else return false;
}
void dfs(int dep) {
	if(dep == n+1) { print_d(); fprintf(fout, "\n"); ans++; return; }
	for(int i = 1; i <= n; i++) if(!vis[i]) {
		if(dep == 1) { vis[i] = true; d[dep] = i; dfs(dep+1); vis[i] = false; }
		else if(check(d[dep-1]+i)) { vis[i] = true; d[dep] = i; dfs(dep+1); vis[i] = false; }
	}
}
int main() {
	fin = fopen("dfs3.in", "r");
	fout = fopen("dfs3.out", "w");
//	fout = stdout;
	fscanf(fin, "%d", &n);
	dfs(1);
	fprintf(fout, "%d", ans);
	return 0;
}