using namespace std;
#include<fstream>
#include<stdio.h>
#define Nmax 128
#define base 10000

int R[Nmax],NR,P;
int Sol[30],Nsol;
int C[15][30],Nc[15],A[30],Na,B[30],Nb;

int inmult()
{
int i,j,k,t;
memset(C,0,sizeof C);

Nc[0]=Nsol;
for(i=1;i<=Nsol;i++) C[0][i]=Sol[i];

for(k=1; (1<<k) <= P; k++)
   {
   //C[k-1] * C[k-1]
   Nc[k]=0;
   for(i=1;i<=Nc[k-1];i++)
       {
       for(j=1,t=0; j<=Nc[k-1] || t; j++, t/=base)
           C[k][i+j-1] = (t+= C[k][i+j-1] + C[k-1][i]*C[k-1][j] ) % base;                          
       if(i+j-2 > Nc[k]) Nc[k]=i+j-2;
       if(Nc[k] > NR) return 1;
       }      
   }
   
memset(A,0,sizeof A);
Na=1;
A[1]=1;

for(k=0; (1<<k) <= P; k++)
   if( ((1<<k)&P) )
      {
      memset(B,0,sizeof B);
      Nb=0;
      for(i=1;i<=Na;i++)
         {
         for(j=1,t=0; j<=Nc[k] || t; j++, t/=base)
             B[i+j-1] = (t+= B[i+j-1] + A[i]*C[k][j]) % base;
         if(i+j-2>Nb) Nb=i+j-2;
         if(Nb > NR) return 1;
         }                  
         
      Na=Nb;
      memcpy(A,B,sizeof A);
      }
      
if(Na > NR) 
   return 1;
if(Na < NR) 
   return -1;
   
i=Na;
while(i && A[i]==R[i]) i--;

if(i==0) return 0;
if(A[i]>R[i]) return 1;
return -1;   
}

int cauta()
{
//pentru primul element
int li,lf,mij,sol,val,k;

li=Sol[Nsol];
lf=9999;

while(li<=lf)
  {
  mij=(li+lf)>>1;
  Sol[Nsol]=mij;
  
  val= inmult();
  if(val==0)
     return 1;
     
  if(val<0)
     {
     sol=mij;
     li=mij+1;      
     }
  else
     lf=mij-1;
  }
Sol[Nsol]=sol;

//pentru restul 
for(k=Nsol-1;k;k--)
  {
  li=0;lf=9999;
  
  while(li<=lf)
    {
    mij=(li+lf)>>1;
    Sol[k]=mij;
    
    val=inmult();
    if(val==0)
      return 1;
    if(val<0)
       {
       sol=mij;
       li=mij+1;      
       }
    else
       lf=mij-1;
    }      
    
  Sol[k]=sol;           
  }
  
return 0;    
}

int init()
{
memset(Sol,0,sizeof Sol);
Nsol=1;
Sol[1]=1;

while( inmult() < 0 )
   {
   if(Sol[Nsol]==1000)
       {
       Sol[Nsol]=0;
       Sol[++Nsol]=1;                
       }    
   else
       Sol[Nsol] *= 10;
   }     
   
if(inmult() == 0 )
   return 0;

if(Sol[Nsol]==1)
   {
   Sol[Nsol]=0;
   Sol[--Nsol]=1000;             
   }
else
   Sol[Nsol] /= 10;
   
return -1;
}

int main()
{
FILE *fin=fopen("numere2.in","r"),
     *fout=fopen("numere2.out","w");
     
char ch;
int i;

NR=0;
ch=fgetc(fin);
while('0'<=ch && ch<='9')
  {
  R[++NR]=ch-'0';
  ch=fgetc(fin);
  }
  
//interschimbare
for(i=1;i<=NR/2;i++)
   R[i]^=R[NR-i+1], R[NR-i+1]^=R[i], R[i]^=R[NR-i+1];

//formare numar
for(i=1;i<=NR;i+=4)
   R[i/4+1]= R[i+3]*1000+R[i+2]*100+R[i+1]*10+R[i];
NR=i/4;
   
//solve
for(P=340;P;P--)
  {
  if(init() == 0 ) 
     break;      
  if(cauta())
     break;               
  }
  
fprintf(fout,"%d",Sol[Nsol]);
for(i=Nsol-1;i;i--) fprintf(fout,"%04d",Sol[i]);
fprintf(fout,"\n");
fprintf(fout,"%d\n",P);

fclose(fout);
fclose(fin);
return 0;
}