暴力法：

#include <iostream>
#include <cmath>
#include <map>
#include <cstdio>

using namespace std;


typedef __int64 LL;
const  LL M = 2147483649;
map<LL,LL> G;


LL pows(LL a,LL b)
{
	LL result = 1;
	while(b--)
	{
		result *= a;
	}
	return result;
}
void init()
{
	for(LL i=2;i<=200000;i++)
	{   
		for(int k=0;k<2;k++)
		{
			i = - i;
		for(LL j=2;j<=31;j++)
		{
			LL temp = pows(i,j);
			if(temp>M||temp<-M)break;
			if(G[temp]==0)G[temp]=j;//这个其实很缺陷
		}
		}
	}
}
int main()
{
   init();
   int n;
   while(cin>>n)
   {
	   if(n==0)break;
	   LL en = G[(LL)n];//同样很缺陷！！！
	   if(en==0)puts("1");
	   else printf("%I64d\n",en);
   }
   return 0;
}