#include<stdio.h>
#include<string.h>
#define baza 10000
#define cif_afisare "%04d"
#define nmax 320/4
int p;
int sol[nmax],st[nmax],dr[nmax],m[nmax],cm[nmax],x[nmax];

void read()
{
	freopen("numere2.in","r",stdin);
	freopen("numere2.out","w",stdout);
	char vinit[nmax];
	gets(vinit+1);
	sol[0]=vinit[0]=strlen(vinit+1);
	int i,j,lim=(vinit[0]+1)/2;
	for(i=1;i<=lim;i++)
	{
		sol[vinit[0]-i+1]=vinit[i]-'0';
		sol[i]=vinit[vinit[0]-i+1]-'0';
	}
	int v[nmax];
	memset(v,0,sizeof(v));
	lim=sol[0];
	for(i=1;i<=lim;i=i+4)
		for(j=i+3;j>=i;j--)
			v[i/4+1]=v[i/4+1]*10+sol[j];
	v[0]=lim/4+1;
	if(lim%4==0)
		v[0]--;
	memcpy(sol,v,sizeof(v));
}

void inc_st(int x)
{
	int i,lim=st[0];
	for(i=1;i<=lim || x;i++)
	{
		x=x+st[i];
		st[i]=x%baza;
		x=x/baza;
	}
	st[0]=i-1;
}

void make_m()
{
	int i,lim=dr[0],t=0;
	for(i=1;i<=lim || t;i++)
	{
		t=t+st[i]+dr[i];
		m[i]=t%baza;
		t=t/baza;
	}
	m[0]=i-1;
	for(i=m[0];i>0;i--,t%=2)
		m[i]=(t=t*baza+m[i])/2;
	for(;m[0]>1 && !m[m[0]];m[0]--);
}

void inmcm()
{
	int i,j,t,lim=cm[0],c[nmax];
	memset(c,0,sizeof(c));
	for(i=1;i<=lim;i++)
	{
		for(t=0,j=1;j<=lim || t;j++,t/=baza)
			c[i+j-1]=(t+=c[i+j-1]+cm[i]*cm[j])%baza;
		if(i+j-2>c[0])
			c[0]=i+j-2;
	}
	memcpy(cm,c,sizeof(c));
}

void inmx()
{
	int i,j,t,c[nmax];
	memset(c,0,sizeof(c));
	for(i=1;i<=x[0];i++)
	{
		for(t=0,j=1;j<=cm[0] || t;j++,t/=baza)
			c[i+j-1]=(t+=c[i+j-1]+x[i]*cm[j])%baza;
		if(i+j-2>c[0])
			c[0]=i+j-2;
	}
	memcpy(x,c,sizeof(c));
}

void ridicare()
{
	int cp=p;
	x[0]=1;
	x[1]=1;
	memcpy(cm,m,sizeof(m));
	while(cp>1)
	{
		if(cm[0]+x[0]>sol[0])
		{
			memcpy(cm,sol,sizeof(sol));
			cm[0]++;
			return;
		}
		if(cp&1)
			inmx();//inm x cu cm
		inmcm();//inm cm cu cm
		cp=cp>>1;
	}
	inmx();//inm x cu cm
	memcpy(cm,x,sizeof(x));
}

int difsol()
{
	int i,lim=cm[0];
	if(cm[0]<sol[0])
		return -1;
	for(i=lim;i>=0;i--)
		if(cm[i]!=sol[i])
			return cm[i]-sol[i];
	return 0;
}

int exista()
{
	ridicare();
	int dif=difsol();
	if(dif==0)
		return 0;
	if(dif>0)
		return 1;
	return -1;
}

int difcb()
{
	int i,lim=st[0];
	for(i=0;i<=lim;i++)
		if(st[i]!=dr[i])
			return 1;
	return 0;
}

int exista_baza()
{
	memset(st,0,sizeof(st));
	st[0]=1;
	st[1]=2;
	memcpy(dr,sol,sizeof(sol));
	while(difcb())
	{
		make_m();
		if(exista()>=0)
			memcpy(dr,m,sizeof(m));
		else
		{
			memcpy(st,m,sizeof(m));
			inc_st(1);
		}
	}
	make_m();
	if(exista()==0)
		return 1;
	return 0;
}

void rez()
{
	for(p=50;p>=1;p--)
		if(exista_baza())
			break;
	int i,lim=m[0];
	printf("%d",m[lim]);
	for(i=lim-1;i>=1;i--)
		printf(cif_afisare,m[i]);
	printf("\n%d\n",p);
}

int main()
{
	read();
	if(sol[0]==1 && sol[1]==1)
	{
		printf("1\n1\n");
		return 0;
	}
	rez();
	return 0;
}