a[10030],s=1e4,i,j,k;main(n){for(a[1]=scanf("%d",&n);s--;)for(i=0;i++<n;a[i]&&(!a[i+j]|a[i+j]>a[i]?a[i+j]=a[i]+1:0,!a[i-j]|a[i-j]>a[i]?a[i-j]=a[i]+1:0),j=0)for(k=i;k;k&=k-1)j++;i=!printf("%d",a[n]-!a[n]);}