a[25000]={0,1},m=5e4,n,i,j,k,s=1;main(x){for(scanf("%d",&n);!a[n]&&s;x++){memcpy(a+m,a,m);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);}i=!printf("%d",a[n]?x:-1);}