#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpii;

template<class T> using vec = vector<T>;
template<class T> using uset = unordered_set<T>;
template<class K, class V> using umap = unordered_map<K, V>;

const int LIM = 1e9+7;
bitset<LIM> isPrime;
void eratosthenes() {
    const int S = (int)round(sqrt(LIM)), R = LIM / 2;
    vi sieve(S+1);
    vector<pii>cp;
    for(int i = 3; i <= S; i+=2) if(!sieve[i]) {
            cp.push_back({ i, i * i / 2});
            for (int j = i*i; j <= S; j += 2*i) sieve[j] = 1;
        }
    for(int L = 1; L <= R; L += S) {
        array<bool, S> block{};
        for (auto & [p, idx] : cp)
            for(int i = idx; i < S+L; idx = (i+=p)) block[i-L] = 1;
        rep(i, 0, min(S, R-L))
            if(!block[i]) isPrime[(L + i) * 2 + 1] = true;
    }

    isPrime[2] = true;
}

int dfs(int n);
int memo(int n) {
    static umap<int, int> memo;
    if (!memo.count(n)) memo[n] = dfs(n);
    return memo[n];
}

int dfs(int n) {
    if (!isPrime[n]) return 0;
    int bestLen = 0;

    for (int i = 1; i <= n; i *= 10) {
        int newN = n % i + (n / i / 10 * i);
        bestLen = max(bestLen, memo(newN));
    }

    return bestLen + 1;
}

void solve () {
    eratosthenes();

    int n; cin >> n;
    cout << memo(n) << endl;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    ll T = 1;
    //cin >> T;
    rep(i, 0, T) solve();

    return 0;
}