#include<cstdio>
#include<cstring>
using namespace std;
int i,nrcif,i1,baza=10000,n1;
char n2[703];
struct str
{
    int v[6003];
};
str n;
int cmp(str a,str b)
{
    //1 dc a<b
    //0 dc a=b
    //-1 dc a>b
    if(a.v[0]<b.v[0]) return 1;
    if(a.v[0]>b.v[0]) return -1;
    int i,n=a.v[0];
    for(i=n;i>=1;i--)
        if(a.v[i]!=b.v[i]) break;
    if(i>=1)
    {
        if(a.v[i]<b.v[i]) return 1;
        return -1;
    }
    return 0;
}
str suma(str a,str b)
{
    str rez;
    //memset(rez.v,0,sizeof(rez.v));
    int l=a.v[0],t=0,j,i;
    if(a.v[0]>b.v[0])
    {
        for(i=b.v[0]+1;i<=a.v[0];i++)
            b.v[i]=0;
        l=a.v[0];
    }
    else
    if(a.v[0]<b.v[0])
    {
        for(i=a.v[0]+1;i<=b.v[0];i++)
            a.v[i]=0;
        l=b.v[0];
    }
    for(j=1;j<=l;j++)
    {
        rez.v[j]=(a.v[j]+b.v[j]+t)%baza;
        t=(a.v[j]+b.v[j]+t)/baza;
    }
    if(t>0)
    {
        l++;
        rez.v[l]=t;
    }
    rez.v[0]=l;
    return rez;
}
str prod(str a,str b)
{
    str rez,s;
    int t,l,i,j,n,m;
    rez.v[0]=0;
    n=a.v[0];
    m=b.v[0];
    for(i=1;i<=n;i++)
    {
        l=i-1;
        s.v[l]=0;
        t=0;
        for(j=1;j<=m;j++)
        {
            l++;
            s.v[l]=(a.v[i]*b.v[j]+t)%baza;
            t=(a.v[i]*b.v[j]+t)/baza;
        }
        if(t>0)
        {
            l++;
            s.v[l]=t;
        }
        s.v[0]=l;
        rez=suma(rez,s);
    }
    return rez;
}
str pow(str a,int b)
{
    int i;
    str rez;
    rez.v[0]=1;
    rez.v[1]=1;
    for(i=0;(1<<i)<=b;i++)
    {
        if(b&(1<<i)) rez=prod(rez,a);
        if((1<<(i+1))<=b)
            a=prod(a,a);
    }
    return rez;
}
str imp(str a)
{
    str r,re;
    int sf,i,m,nr=0,p;
    m=a.v[0];
    //memset(r.v,0,sizeof(r.v));
    //memset(re.v,0,sizeof(re.v));
    if(a.v[m]==1)
    {
        p=a.v[m]*baza+a.v[m-1];
        sf=m-2;
    }
    else
    {
        p=a.v[m];
        sf=m-1;
    }
    nr=1;
    r.v[1]=p/2;
    p=p%2;
    for(i=sf;i>=1;i--)
    {
        p=p*baza+a.v[i];
        nr++;
        r.v[nr]=p/2;
        p=p%2;
    }
    r.v[0]=nr;
    re.v[0]=nr;
    for(i=1;i<=nr;i++)
        re.v[i]=r.v[nr+1-i];
    return re;
}
int cb(int exp)
{
    str val,p,u,mij;
    int ul,i,v1;
    //memset(p.v,0,sizeof(p.v));
    //memset(u.v,0,sizeof(u.v));
    //memset(mij.v,0,sizeof(mij.v));
    p.v[0]=1;
    p.v[1]=1;
    u.v[0]=nrcif/exp+1;
    if(u.v[0]>nrcif)
    {
        for(i=1;i<u.v[0];i++)
            u.v[i]=0;
        u.v[u.v[0]]=1;
    }
    else
    {
        for(i=0;i<=n.v[0];i++)
            u.v[i]=n.v[i];
    }
    while(cmp(p,u)>=0)
    {
        mij=imp(suma(p,u));
        if(u.v[0]==2)
            u.v[0]=2;
        val=pow(mij,exp);
        v1=cmp(val,n);
        if(v1==1)
        {
            //p=mij+1;
            for(i=0;i<=mij.v[0];i++)
                p.v[i]=mij.v[i];
            ul=1;
            p.v[p.v[0]+1]=0;
            p.v[1]++;
            while(p.v[ul]>=baza)
            {
                p.v[ul+1]+=p.v[ul]/baza;
                p.v[ul]=p.v[ul]%baza;
                ul++;
            }
            if(ul>p.v[0]) p.v[0]=ul;
        }
        else
        if(v1==-1)
        {
            //u=mij-1;
            for(i=0;i<=mij.v[0];i++)
                u.v[i]=mij.v[i];
            ul=1;
            u.v[u.v[0]+1]=0;
            u.v[1]--;
            while(u.v[ul]<0)
            {

                u.v[ul+1]--;
                u.v[ul]=9;
                ul++;
            }
            while(u.v[u.v[0]]==0) u.v[0]--;
        }
        else break;
    }
    if(cmp(p,u)>=0)
    {
        for(i=mij.v[0];i>=1;i--)
            printf("%d",mij.v[i]);
        printf("\n");
        printf("%d\n",exp);
        return 1;
    }
    return 0;
}
int main()
{
freopen("numere2.in","r",stdin);
freopen("numere2.out","w",stdout);
gets(n2+1);
n1=strlen(n2+1);
nrcif=n1;
for(i=n1;i>=1;i=i-4)
{
    n.v[0]++;
    n.v[n.v[0]]=n2[i]-48;
    if(i>1)
        n.v[n.v[0]]=n.v[n.v[0]]+((n2[i-1]-48)*10);
    if(i>2)
        n.v[n.v[0]]=n.v[n.v[0]]+((n2[i-2]-48)*100);
    if(i>3)
        n.v[n.v[0]]=n.v[n.v[0]]+((n2[i-3]-48)*1000);
}
for(i1=58;i1>=1;i1--)
    if(cb(i1)) return 0;
return 0;
}