#include<stdio.h>
#include<string.h>
int n,cp,sol[102];
char s[102];
int st[102],dr[102],m[102];
int v[102];

void read()
{
	freopen("numere2.in","r",stdin);
	freopen("numere2.out","w",stdout);
	gets(s+1);
	n=strlen(s+1);
	int i;
	for(i=1;i<=n;i++)
		v[i]=s[n-i+1]-'0';
	v[0]=n;
}

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

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

void adunare1()
{
	int i;
	st[1]++;
	for(i=1;i<=st[0];i++)
		if(st[i]<9)
		{
			st[i]++;
			return;
		}
		else
		{
			st[i]=0;
			st[i+1]++;
		}
	if(i==st[0]+1)
		st[++st[0]]=1;
}

int mare(int p)
{
	int putere;
	int pr[10002];//pr=m^p
	int i,j,t,C[10002];
	memcpy(pr,m,sizeof(m));
	for(putere=2;putere<=p;putere++)
	{
		memset(C, 0, sizeof(C));
		for (i = 1; i <= m[0]; i++)
		{
			for (t=0, j=1; j <= pr[0] || t; j++, t/=10)
				C[i+j-1]=(t+=C[i+j-1]+m[i]*pr[j])%10;
			if (i + j - 2 > C[0]) C[0] = i + j - 2;
		}
		memcpy(pr, C, sizeof(C));
	}
	
	if(pr[0]<v[0])
		return 0;
	if(pr[0]>v[0])
		return 1;
	for(i=1;i<=pr[0];i++)
		if(pr[i]<v[i])
			return 0;
		else
			if(pr[i]>v[i])
				return 1;
	return -1;
}

void cautare(int p)
{
	memset(st,0,sizeof(st));
	st[0]=1;
	st[1]=1;
	memcpy(dr,v,sizeof(dr));
	while(compar())
	{
		build_m();
		if(mare(p))
		{
			memcpy(dr,m,sizeof(m));
		}
		else
		{
			memcpy(st,m,sizeof(m));
			adunare1();
		}
	}
	build_m();
	if(mare(p)==-1)
	{
		memcpy(sol,m,sizeof(m));
		cp=p;
	}
}

void rez()
{
	int i;
	for(i=150;i>=1 && cp==0;i--)
	{
		cautare(i);
	}
	for(i=sol[0];i>=1;i--)
		printf("%d",sol[i]);
	printf("\n%d\n",cp);
}

int main()
{
	read();
	rez();
	return 0;
}