#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long baza = 100000000LL;
long long p[60], st[60], dr[60], m[60], pow[60];
int lp, lst, ldr, lm, lpow, semn, i, j;
char s[100];
int diferenta()
{
int i;
if (lst < ldr)
return 1;
else
for (i=lst; i>=2; --i)
if (st[i] < dr[i]) return 1;
if (st[1] + 1 >= dr[1]) return 0;
else return 1;
}
int solutie()
{
long long k;
int j;
FILE *f;
f = fopen("numere2.out", "w");
fprintf(f, "%lld", m[lm]);
for (j=lm-1; j>0; --j)
{
k = baza;
while (k > m[k])
{
k = k / 10;
fprintf(f, "%d", 0);
}
if (m[j] != 0) fprintf(f, "%lld", m[j]);
}
fprintf(f, "\n");
fprintf(f, "%d", i);
fclose(f);
return 0;
}
int egal()
{
int i;
if (lpow < lp)
return -1;
else if (lpow > lp)
return 1;
else
for (i=lp; i>0; --i)
if (pow[i] < p[i])
return -1;
else if (pow[i] > p[i]) return 1;
return 0;
}
int putere(int exp)
{
int k, i, j, semn;
long long r, rr, aux[60];
rr=0;
lpow=lm;
memcpy(aux, m, sizeof(m));
for (i=2; i<=exp; ++i)
{
memset(pow, 0, sizeof(pow));
semn = 1;
for (j=1; j<=lm; ++j)
{
for (k=1; k<=lpow; ++k)
{
r = (m[j] * aux[k] + rr + pow[j + k - 1]) / baza;
pow[j + k - 1] = (m[j] * aux[k] + rr + pow[j + k - 1]) % baza;
rr = r;
}
if (rr > 0)
{
pow[j + k-1]=rr;
if (j + k-1 == lm + lpow) semn = 0;
rr = 0;
}
}
lpow = lm + lpow - semn;
if (lpow > lp) return 0;
memcpy(aux, pow, sizeof(pow));
}
return 0;
}
int medie()
{
long long r, rr;
int i;
rr = 0;
lm = ldr;
for (i=1; i<=ldr; ++i)
{
r = (st[i] + dr[i] + rr) / baza;
m[i] = (st[i] + dr[i] + rr) % baza;
rr = r;
}
if (rr > 0)
{
++lm;
m[lm] = rr;
rr = 0;
}
for (i=lm; i>0; --i)
{
r = (baza * rr + m[i]) % 2;
m[i] = (baza * rr + m[i]) / 2;
rr = r;
}
if (m[lm] == 0) --lm;
return 0;
}
int citire()
{
FILE *f;
int length, ll, nr, b;
f = fopen ("numere2.in", "r");
fscanf (f, "%s", s);
fclose(f);
length=strlen(s);
nr = 0; b = 1; lp = 0;
for (i=length-1; i>=0; --i)
{
if (nr+b*(s[i]-'0') < baza)
{
nr += b*(s[i]-'0');
b *= 10;
}
else
{
++lp;
p[lp] = nr;
nr = (s[i]-'0');
b = 10;
}
}
++lp; p[lp] = nr;
return 0;
}
int main()
{
citire();
for (i=350; i>1; --i)
{
lst = 1;
st[1] = 2;
ldr = (lp / i) + 2;
dr[ldr] = 1;
while (diferenta())
{
medie();
putere(i);
semn = egal();
switch (semn)
{
case -1:
{
lst = lm;
memcpy(st,m,sizeof(m));
break;
}
case 1:
{
ldr = lm;
memcpy(dr,m,sizeof(m));
break;
}
case 0:
{
solutie();
return 0;
break;
}
}
}
memcpy(m,st,sizeof(st));
putere(i);
if (egal==0) { solutie(); return 0; }
}
lm = lp;
memcpy(m,p,sizeof(p));
i=1;
solutie();
return 0;
}