#include <stdio.h>
#include <string.h>
#define MAX 250

typedef int NrMare[MAX];

NrMare p, x;

void init(NrMare a){
	int i;
	for (i=0; i<MAX; ++i) a[i]=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;
	char s[MAX];
	FILE *f=fopen ("numere2.in", "r");
	fscanf (f, "%s\n", &s);
	fclose(f);
	p[0]=strlen(s);
	for (i=p[0]; i>=1; --i) p[p[0]-i+1]=s[i-1]-'0';
}

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);
		produs(a, prod, prod2);
		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;
	init(unu);
	left[0]=left[1]=1; right[1]=0; right[0]=100;
	for (i=2; i<100; ++i) left[i]=right[i]=0; right[100]=1; left[100]=0;
	Cpy (unu, left);

	while (compara(left, right) <= 0) {
		init(aux);
		for (i=0; i<110; ++i) s[i]=0;
		suma(left, right, s);
		imp2(s);
		Cpy(mid, s);
		pow(s, exp);
		if (compara(s, p) < 0) { suma(mid, unu, aux); Cpy(left, aux); }
		else if (compara(s, p)>0) { dif(mid, unu, aux); Cpy(right, aux); }
		else { Cpy(x, mid); return 1;}
	}
	return -1;
}

void afis(NrMare x, int exp) {
	FILE *g=fopen("numere2.out", "w");
	int i;
	for (i=x[0]; i; --i)
		fprintf(g, "%d", x[i]);
	fprintf(g, "\n%d\n", exp);
	fclose(g);
}

int main() {
	citire();

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

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


	return 0;
}