#include<iostream>
using namespace std;
#include<math.h>
int main()
{
    long x;
    int calculate(long x);
    while(cin>>x,x!=0)
         cout<<calculate(x)<<endl;
    system("pause");
    return 0;
}

int calculate(long x)
{
    float b;
    float p;
    for( b=2; b<= x; b++)
    {
         for( p=1; p< 32; p++)
         {
              if((long)pow(b,p)>x) break;
              if(x== (long)pow(b,p))
              return p;
         }
    }
}