#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 50
#define BASE 10000

typedef int NrMare[MAX];

NrMare p, x;

void init(NrMare a){
	int i;
	for (i=0; i<MAX; ++i) a[i]=0;
}

void div(NrMare A, int B)
{
		int i, t = 0;
		for (i = A[0]; i > 0; i--, t %= B)
				  A[i] = (t = t * BASE + A[i]) / B;
		for (; A[0] > 1 && !A[A[0]]; A[0]--);
}


void add(NrMare A, NrMare B)
{
		int i, t = 0;
		for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=BASE)
				  A[i] = (t += A[i] + B[i]) % BASE;
		A[0] = i - 1;
}


void mul(NrMare A, NrMare B)
{
		int i, j, t, C[MAX];
		memset(C, 0, sizeof(C));
		for (i = 1; i <= A[0]; i++)
		{
				  for (t=0, j=1; j <= B[0] || t; j++, t/=BASE)
							 C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%BASE;
				  if (i + j - 2 > C[0]) C[0] = i + j - 2;
		}
		memcpy(A, C, sizeof(C));
}


void sub(NrMare A, NrMare B)
{
		int i, t = 0;
		for (i = 1; i <= A[0]; i++)
				  A[i] += (t = (A[i] -= B[i] + t) < 0) * BASE;
		for (; A[0] > 1 && !A[A[0]]; A[0]--);
}


/*void suma (NrMare a, NrMare b, NrMare x){
	int i, t=0, max, na=a[0], nb=b[0];
	if (na<nb) {max=nb; for (i=na+1; i<=nb; i++) a[i]=0; }
		else {max=na; for (i=nb+1; i<=na; i++) b[i]=0; }
	for (i=1; i<=max; i++) {
		x[i]=(a[i]+b[i]+t)%10;
		t= (a[i]+b[i]+t)/10;
		}
	if (t) x[i]=t;
	else i--;
	x[0]=i;
	for (i=x[0]+1; i<MAX; ++i) x[i]=0;
} */

void citire(){
	int i, l, aux;
	char s[150];
	FILE *f=fopen ("numere2.in", "r");
	fscanf (f, "%s\n", &s);
	fclose(f);
	while ((l=strlen(s)) > 4)
		p[++p[0]]= atoi(s+l-4), s[l-4]=0;
	if (s) p[++p[0]]= atoi(s);
	//for (i=1; i<=p[0]/2; ++i) aux=p[i], p[i]=p[p[0]-i+1], p[p[0]-i+1]=aux;
}

/*void produs (NrMare n, NrMare n1, NrMare p) {
	int i, j, t, cif;
	for (i=1; i<=n1[0]; i++){
		for (t=0, j=1; j<=n[0]; ++j){
			cif=p[i+j-1]+n[j]*n1[i]+t;
			p[i+j-1]=cif%10;
			t=cif/10;
		}
		if (t) p[i+j-1]=t;
	}
	p[0]=n[0]+n1[0]-1;
	if (p[p[0]+1]) ++p[0];
	for (i=p[0]+1; i<MAX; ++i) p[i]=0;
} */

/*void imp2(NrMare a){
	int i, r=0, aux, na=a[0];
	for (i=na; i>0; i--){
		aux=a[i];
		a[i]=(r*10+a[i])/2;
		r=aux%2;
		}
	i=na;
	while (!a[i]) i--;
	a[0] = i;
	for (i=a[0]+1; i<MAX; ++i) a[i]=0;
} */

int compara (NrMare a, NrMare b){
	int i, na=a[0], nb=b[0];
	if (na<nb) return -1;
	if (na>nb) return 1;
	for (i=na; i>0 && a[i]==b[i]; i--);
	if (i<=0) return 0;
	if (a[i]<b[i]) return -1;
	return 1;
}


/*NrMare pow (NrMare a, int n) {
	NrMare x, prod, prod2;
	for (int i = 0; i<MAX; ++i) prod[i]=prod2[i]=0;
	if (n==1) return a;
	x = pow(a, n/2);
	produs(x, x, prod);
	if (x%2==0) return prod;
	else { produs(a, prod, prod2); return prod2; }
}*/

void Cpy(NrMare dest, NrMare src) {
	int i;
	dest[0]=src[0];
	for (i=1; i<=src[0]; ++i)
		dest[i]=src[i];
	for(i=dest[0]+1; i<MAX; ++i) dest[i]=src[i]=0;
}

void pow (NrMare a, int n) {
	NrMare prod, prod2;
	int i;
	for (i = 0; i<MAX; ++i) prod[i]=prod2[i]=0;
	prod[0]=prod[1]=1;
	for (i = 0; i<n && compara(prod, p)<=0; ++i){
		//init(prod2);
		mul(prod, a);
		//Cpy(prod, prod2);
	}
	Cpy(a, prod);
}

/*void dif (NrMare n, NrMare unu, NrMare n1) {
	int i, t=0;
	for (i=1; i<=n[0]; ++i) {
		n1[i]=n[i]-unu[i]+t;
		if (n1[i]<0)
			n1[i]+=10, t=-1;
		else t=0;
	}
	i--;
	while (i && !n1[i]) i--;
	n1[0]=i;
	for (i=n1[0]+1; i<MAX; ++i) n1[i]=0;
} */



int find (int exp) {
	NrMare left, right, mid, s, aux, unu;
	int i, C;
	init(unu);
	left[0]=left[1]=1; right[1]=0; right[0]=17;
	for (i=2; i<=16; ++i) left[i]=right[i]=0; right[17]=1; left[17]=0;
	Cpy (unu, left);

	while (compara(left, right) <= 0) {
		init(aux);
		for (i=0; i<17; ++i) s[i]=0;
		Cpy(s, left); add(s, right);
		div(s, 2);
		Cpy(mid, s);
		pow(s, exp);
		C = compara(s, p);
		if (C < 0) { add(mid, unu); Cpy(left, mid); }
		else if (C > 0) { sub(mid, unu); Cpy(right, mid); }
		else { Cpy(x, mid); return 1;}
	}
	return -1;
}

void afis(NrMare x, int exp) {
	FILE *g=fopen("numere2.out", "w");
	int i, nr, aux, j;
	for (i=x[0]; i; --i)
		{
		nr=0; aux=x[i]; while (aux) nr++, aux/=10;
		if (nr<6&&i<x[0]) for (j=0; j<4-nr; ++j) fprintf(g, "0");
		fprintf(g, "%d", x[i]);
	}
	fprintf(g, "\n%d\n", exp);
	fclose(g);
}

int main() {
	citire();

	int exp, found=0;
	for (exp = 150; exp>=1 && !found; --exp)
		if (find(exp) == 1)
			found = 1;

	if (found)
		afis(x, exp+1);


	return 0;
}