#include <iostream>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>

static std::unordered_map<int, bool> primes;
static std::unordered_map<int, int> dfs_memo;

bool isPrime(int num) {
    if (num == 1)
        return false;

    if (num % 2 == 0)
        return false;

    auto it = primes.find(num);

    if (it == primes.end()) {
        for (int i = 3; i < std::sqrt(num) + 1; i += 2) {
            if (num % i == 0) {
                primes[num] = false;
                return false;
            }
        }

        primes[num] = true;
        return true;
    } else
        return it->second;

}

int dfs(int num, int found) {
    auto it = dfs_memo.find(num);
    if (it != dfs_memo.end())
        return found + it->second;

    if (!isPrime(num))
        return found;
    else
        found++;

    int max_found = 0;

    std::set<int> seen;
    std::string snum = std::to_string(num);
    int num_size = snum.size();
    for (int i = 0; i < num_size; i++) {
        std::string next;
        next.reserve(num_size - 1);

        for (int j = 0; j < i; j++)
            next.push_back(snum[j]);

        for (int j = i + 1; j < num_size; j++)
            next.push_back(snum[j]);

        int inext = std::atoi(next.c_str());

        if (seen.contains(inext))
            continue;

        // std::cout << next << std::endl;
        // std::cout << inext << std::endl;

        int res = dfs(inext, 0);
        max_found = std::max(max_found, res);
        seen.insert(inext);
    }

    dfs_memo[num] = max_found + 1;
    return found + max_found;
}

int main() {
    int number;
    std::cin >> number;
    int found_max = dfs(number, 0);
    std::cout << found_max << std::endl;
    // while (1) {
    // }
    return 0;
}