#include <bits/stdc++.h>

using namespace std;
const int N = 100;
int n;
int cnt;
int st[N];
vector<int> path;

//判断一个数是不是质数
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) {
        if (isPrime(1 + path.back())) {
            cnt++;
            for (int i = 0; i < path.size(); i++)
                cout << path[i] << " ";
            cout << endl;
        }
        return;
    }
    //摆放当前位置数字
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            if (isPrime(i + path.back())) {
                path.push_back(i);
                st[i] = true;
                dfs(step + 1);
                st[i] = false;
                path.pop_back();
            }
        }
    }
}

int main() {
    cin >> n;
    //素数环从1开始
    path.push_back(1);
    st[1] = true;
    dfs(2);

    cout << cnt << endl;
    return 0;
}