#include<stdio.h>
#include<math.h>

int main(){
	__int64 x,z;
	int i,y,p;
	while(1){
		scanf("%I64d",&x);
		if(x==0)break;
		if(x==1||x==-1)continue;
		p=1;
		if(x>0){
			for(i=2;;i++){
				y=(int)pow(x*1.0,1.0/i);
				if(y<2)break;
				z=(__int64)pow(y+0.0,i);
				if(x==z)p=i;
				else{
					z=(__int64)pow(y+1.0,i);
					if(x==z)p=i;
				}
			}
		}else{
			x=-x;
			for(i=3;;i+=2){
				y=(int)pow(x*1.0,1.0/i);
				if(y<2)break;
				z=(__int64)pow(y+0.0,i);
				if(x==z)p=i;
				else{
					z=(__int64)pow(y+1.0,i);
					if(x==z)p=i;
				}
			}
		}
		printf("%d\n",p);
	}
	return 0;
}