#include"stdio.h"
#include"math.h"
main(){
	__int64 a,b;
	double i,j,f,m;
    while(scanf("%I64d",&a)){
        b=fabs(a);
		if(!a) break;
		else if(b==4294967296)printf("32\n");
		else if(b==2147483648&&a<0)printf("1\n");
		else if(b==2147483648&&a>0)printf("31\n");
		else{
		a>0?m=1:m=2;
		for(i=33;i>=1;i=i-m){
			f=pow(b,1.0/i);
			if(fabs(f-floor(f))<1e-20||fabs(f-ceil(f))<1e-20){
				printf("%0.0f\n",i);
				break;
			}
		}
		}
	}
}