d['~~'],j,k;main(i,n){for(*d=scanf("%d",&n);k=i++<=n;){for(;i%++k&&k*k<=i;);for(j=n;k*k>i&j>=i;--j)d[j-i]?d[j]=fmax(d[j],d[j-i]+1):0;}j=!printf("%d",d[n]-1);}