#include <bits/stdc++.h>

using namespace std;
int n;
const int N = 110;
int a[N];
int cnt;
bool st[N];
//判断一个数是不是质数
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;
    return true;
}
void dfs(int step) {
    if (step == n + 1) {
        for (int i = 1; i <= n; i++)
            printf("%d ", a[i]);
        cnt++;
        printf("\n");
        return;
    }
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            bool f = false;
            if (isPrime(a[step - 1] + i)) {
                if (step < n)
                    f = true;
                else if (isPrime(i + 1))
                    f = true;
            }
            if (f) {
                st[i] = true;
                a[step] = i;
                dfs(step + 1);
                st[i] = false;
            }
        }
    }
}
int main() {
    cin >> n;
    a[1] = 1;
    dfs(2);
    printf("%d", cnt);
    return 0;
}