#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    double b;
    int n,i,k,x;
    __int64 temp;
    while(cin>>n&&n!=0)
    {              
        if(n<0)x=2,n=abs(n);else x=1;
        k=0;
        for(temp=1;temp<n;temp*=2)k++;
        if(x==2&&k%2==0)k-=1;
        for(i=k;i>=1;i-=x)
        {
            b=pow(n,double(1)/i);             
            if(int(b)==b)break;
            double dn=double(n);
            double dr=pow(double(int(b+0.5)),double(i));
            if(dr==dn)break;              
        }  
        cout<<i<<endl;             
    }
    
    return 0;
}