#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
using namespace std;
const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1000000 + 666;
bool is_p[maxn];
int prime[maxn], len, dp[maxn];
int main()
{
// ifstream cin ("aaa.txt");
memset (is_p, true, sizeof (is_p));
len = 0;
for (int i = 2; i <= maxn - 66; i++)
{
if (is_p[i])
{
prime[len++] = i;
for (int j = 2; j * i <= maxn- 66; j++)
is_p[j*i] = false;
}
}
fill (dp, dp + maxn, INF);
dp[1] = 0;
for (int i = 1; i <= 1000000; i++)
{
for (int j = 0; j < len; j++)
{
if (prime[j] * i > 1000000)
break;
dp[i*prime[j]] = min (dp[i*prime[j]], dp[i] + 1);
}
dp[i+1] = min (dp[i+1], dp[i] + 1);
}
int n;
while (cin >> n)
{
cout << dp[n] << endl;
}
return 0;
}