#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#include<queue>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x)) #define qwq(x) for(edge *o=head[x];o;o=o->next)const int nmax=2e6+5;const int maxn=1e7+5;const int inf=0x7f7f7f7f;struct node{	int x,dist;	node(int x,int dist):x(x),dist(dist){};	node(){};	bool operator<(const node&rhs)const{	  return dist>rhs.dist;}};priority_queue<node>q;int dist[nmax];const int a[]={2,3,5,7,9,11,13};int dij(int x){	clr(dist,0x7f);dist[1]=0;q.push(node(1,0));	node o;int tx,td,to;	while(!q.empty()){		o=q.top();q.pop();tx=o.x;td=o.dist;		if(dist[tx]!=td) continue;		rep(i,0,5){			to=tx*a[i];			if(to<x+10&&dist[to]>td+a[i]){				dist[to]=td+a[i];q.push(node(to,td+a[i]));			}		}		if(tx&&dist[tx-1]>dist[tx]+1){			dist[tx-1]=dist[tx]+1;q.push(node(tx-1,dist[tx-1]));		}	}	 	return dist[x];}int main(){	int n;scanf("%d",&n);	printf("%d\n",dij(n));	return 0;}