#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 2000010
using namespace std;
typedef pair<int,int>pii;
const int prime[10]={0,2,3,5,7,11,13};
const int cnt=6;
struct node{int y,next,v;}e[MAXN<<1];
int n,len,Link[MAXN],vis[MAXN],dis[MAXN];
priority_queue<pii,vector<pii>,greater<pii> >q;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(int x,int y,int v){e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;}
void pre(){
	for(int i=1;i<=n;++i)
		for(int j=1;j<=cnt&&prime[j]*i<=n+4;++j)
			insert(i,i*prime[j],prime[j]);
	for(int i=2;i<=n+4;++i) insert(i,i-1,1);
}
void dijkstra(){
	memset(dis,10,sizeof(dis));
	q.push(make_pair(0,1));  vis[1]=1;  dis[1]=0;
	while(!q.empty()){
		int v=q.top().first,x=q.top().second;  q.pop();
		for(int i=Link[x];i;i=e[i].next){
			if(dis[x]+e[i].v<dis[e[i].y]){
				dis[e[i].y]=dis[x]+e[i].v;
				if(!vis[e[i].y])  q.push(make_pair(dis[e[i].y],e[i].y)),vis[e[i].y]=1;
			}
		}
		vis[x]=0;
	}
	printf("%d\n",dis[n]);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  pre();  dijkstra();
	return 0;
}