#include <stdio.h>
#include <algorithm>
#define mx 1000
#define bz_num 10000

using namespace std;

char s[mx];
int init[mx], p[mx], u[mx], a[mx], mij[mx];

int compara(int vct1[], int vct2[])
{
	if (vct1[0] > vct2[0])
		return 1;
	else if (vct2[0] > vct1[0])
		return -1;
	for (int i = vct1[0]; i; i--)
		if (vct1[i] > vct2[i])
			return 1;
		else if (vct2[i] > vct1[i])
			return -1;
	return 0;
}

void aduna(int *vct_sum, int vct_ter[])
{
	int i, t = 0;
	for (i = 1; i <= max(vct_sum[0], vct_ter[0]) || t; i++, t /= bz_num)
		vct_sum[i] = (t += vct_sum[i] + vct_ter[i]) % bz_num;
	vct_sum[0] = i - 1;
}

void scade(int *vct_dif, int vct_scz[])
{
    int i, t = 0;
    for (i = 1; i <= vct_dif[0]; i++)
         vct_dif[i] += (t = (vct_dif[i] -= vct_scz[i] + t) < 0) * bz_num;
    for (; vct_dif[0] > 1 && !vct_dif[vct_dif[0]]; vct_dif[0]--);
}

void imparte_mic(int *cat, int imp)
{
	int i, t = 0;
	for (i = cat[0]; i; i--, t %= imp)
		cat[i] = (t = t * bz_num + cat[i]) / imp;
	for (; cat[0] > 1 && !cat[cat[0]]; cat[0]--);
}

void inmult(int *vct_prod, int vct_fact[])
{
      int i, j, t, temp[mx];
      memset(temp, 0, sizeof(temp));
      for (i = 1; i <= vct_prod[0]; i++)
      {
              for (t = 0, j = 1; j <= vct_fact[0] || t; j++, t /= bz_num)
                      temp[i + j - 1] = (t += temp[i + j - 1] + vct_prod[i] * vct_fact[j]) % bz_num;
              if (i + j - 2 > temp[0])
				  temp[0] = i + j - 2;
      }
      memcpy(vct_prod, temp, sizeof(temp));
}

int cauta(int pt)
{
	int r[mx], st[mx];
	if (compara(p, u) == 1)
		return 0;
	memcpy(mij, p, sizeof(p));
	aduna(mij, u);
	imparte_mic(mij, 2);
	memcpy(a, mij, sizeof(mij));
	memset(r, 0, sizeof(r));
	r[0] = r[1] = 1;
	int ok = -2, pu = pt;
	for (; pu > 1; pu >>= 1)
	{
		if (pu & 1)
			inmult(r, a);
		inmult(a, a);
		memcpy(st, a, sizeof(a));
		inmult(st, r);
		ok = compara(st, init);
		if (ok == 1)
			break;
	}
	inmult(a, r);
	ok = compara(a, init);
	if (!ok && pu == 1)
		return 1;
	if (ok == 1)
	{
		memcpy(u, mij, sizeof(mij));
		memset(mij, 0, sizeof(mij));
		mij[0] = mij[1] = 1;
		scade(u, mij);
		return cauta(pt);
	}
	else
	{
		memcpy(p, mij, sizeof(mij));
		memset(mij, 0, sizeof(mij));
		mij[0] = mij[1] = 1;
		aduna(p, mij);
		return cauta(pt);
	}
}

int main()
{
	freopen("numere2.in","r",stdin);
	freopen("numere2.out","w",stdout);
	gets(s);
	int t = 1, x = 0, of = 0;
	for (int i = strlen(s) - 1; i >= 0; i--)
	{
		x = x + (s[i] - '0') * t;
		t *= 10;
		of = 1;
		if (t == bz_num)
		{
			init[++init[0]] = x;
			t = 1;
			x = 0;
			of = 0;
		}
	}
	if (of)
		init[++init[0]] = x;
	for (int maxc = 45; maxc; maxc--)
	{
		memset(p, 0, sizeof(p));
		p[0] = p[1] = 1;
		memcpy(u, init, sizeof(init));
		if (cauta(maxc))
		{
			printf("%d", mij[mij[0]]);
			for (int i = mij[0] - 1; i; i--)
				printf("%04d", mij[i]);
			printf("\n%d\n", maxc);
			fclose(stdin);
			fclose(stdout);
			return 0;
		}
	}
}