a[40000],m=2e4,n,i,j,k,s=1;main(x){a[1]=a[20001]=1;for(scanf("%d",&n);!a[n]&&s;x++){for(s=i=0;i++<n;j=0)if(a[i]){for(k=i;k;k&=k-1)j++;i+j>n|a[i+j]||a[i+j+m]++|s++;i<j|a[i-j]||a[i-j+m]++|s++;}memcpy(a,a+m,m*4);}i=!printf("%d",a[n]?x:-1);}