Deleatable Primes

#include <bits/stdc++.h>
#define int long long

using namespace std;

bool prim(int a) {
    if(a == 0 || a == 1)
        return false;
    if(a == 2 || a == 3)
        return true;
    if(a % 2 == 0 || a % 3 == 0)
        return false;
    int rad = sqrt(a);
    for(int d = 5; d <= rad; d += 6)
        if(a % d == 0 || a % (d + 2) == 0)
            return false;
    return true;
}

int ans;

inline void solve(string& s) {
    if(s.size() == 1) {
        if(strchr("2357", s[0]))
            ++ans;
        return;
    }
    int N = s.size();
    for(int i = 0; i < N; ++i) {
        int val = 0;
        for(int j = 0; j < N; ++j)
            if(j != i)
                val = val * 10 + (s[j] - '0');
        if(prim(val)) {
            string new_s;
            for(int j = 0; j < N; ++j)
                if(j != i)
                    new_s.push_back(s[j]);
            solve(new_s);
        }
    }
}

int32_t main() {
    string s;
    cin >> s;
    solve(s);
    cout << ans;
}