//1730

#include < iostream.h >
#include < math.h >

int main()
{
	double a;
	double i;
	while(1){
		cin>>a;
		if(a==0)return 0;
//		if(a==)
		if(a>=0){
		for( i = 32;i>1;i--)
		{
			double x = pow(a,(1/i));
			if( fabs(x-floor(x))<=0.0000000000001)
				break;
			if( fabs(ceil(x)-x)<=0.0000000000001)
				break;
		}
		cout<<i<<endl;
		}
		else{
		for( i = 31;i>1;i-=2)
		{
			double x = pow(-a,(1/i));
//			cout<<x<<endl;
			if( fabs(x-floor(x))<=0.0000000000001)
				break;
			if( fabs(ceil(x)-x)<=0.0000000000001)
				break;
		}	
		cout<<i<<endl;
		}
	}
	return 0;
}