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

int choice1(int n)
{
    int temp = sqrt(n);
    while (n % temp != 0)
    {
        temp++;
    }
    return temp;
}

int choice2(int n)
{
    return n - 1;
}

int main()
{
    int n;
    cin >> n;
    int turn = 0;
    map<int, bool> number;
    map<int, bool> result;
    number[n] = true;

    bool found = false;
    while (true)
    {
        turn++;
        for (map<int, bool>::iterator it = number.begin(); it != number.end(); it++)
        {
            int res1 = choice1(it->first);
            int res2 = choice2(it->first);
            if (res1 == 0 || res2 == 0)
            {
                found = true;
                break;
            }
            result[res1] = true;
            result[res2] = true;
        }

        if (found) break;

        number.clear();
        number = result;
        result.clear();
    }

    cout << turn;
}