#include<iostream>
#include<math.h>
using namespace std;

int power(int a,int b)
{
	int i;
	int sum=1;
	for(i=0;i<b;i++)
	{
		sum=sum*a;
	}
	return sum;
}
int main()
{
	double n;
	int i,j,k;
	while(cin>>n&&n!=0)
	{
		if(n>0)
		{
			for(i=32;i>=1;i--)
			{
				j=(int)pow(n,1.0/i);
				if(n==power(j,i))
				{
					k=i;
					break;
				}
			}
			cout<<k<<endl;
		}
		else
		{
			n=-n;
			for(i=32;i>=1;i--)
			{
				j=(int)pow(n,1.0/i);
				if(n==power(j,i))
				{
					k=i;
					if(k%2==0)continue;
					break;
				}
			}
			 cout<<k<<endl;
		}
	}
	return 0;
}