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