#include <fstream>
#include <string>
#include <cstring>

using namespace std;

int P[100];
int A[100];
int step[100];
int putere[100];
string Plol;
int Putere_Slow_A[275];
ofstream fout ("numere2.out");

void Add () {
    int i, t = 0;
    for (i=1; i<=A[0] || i<=step[0] || t; i++, t/=10000)
        A[i] = (t += A[i] + step[i]) % 10000;
    A[0] = i - 1;
}

void Mul () {
    int i, t = 0;
    for (i = 1; i <= putere[0] || t; i++, t /= 10000)
        putere[i] = (t += putere[i] << 1) % 10000;
    putere[0] = i - 1;
}

void Mul_Mare () {
    int i, j, t, C[100];
    memset (C, 0, sizeof(C));
    for (i = 1; i <= Putere_Slow_A[0]; i++)
    {
        for (t=0, j=1; j <= A[0] || t; j++, t/=10000)
            C[i+j-1]=(t+=C[i+j-1]+Putere_Slow_A[i]*A[j])%10000;
        if (i + j - 2 > C[0]) C[0] = i + j - 2;
    }
    memcpy (Putere_Slow_A, C, sizeof(C));
}

void Div () {
    int i, t = 0;
    for (i = step[0]; i > 0; i--, t &= 1)
        step[i] = (t = t * 10000 + step[i]) >> 1;
    for (; step[0] > 1 && !step[step[0]]; step[0]--);
}

void Sub () {
      int i, t = 0;
      for (i = 1; i <= A[0]; i++) {
              A[i] -= ((i <= step[0]) ? step[i] : 0) + t;
              A[i] += (t = A[i] < 0) * 10000;
      }
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

void Citire () {
    ifstream fin ("numere2.in");
    fin >> Plol;
    int N = Plol.size (), i, lol = 0;
    for (i = N - 1; i >= 4; i -= 4)
    {
        lol++;
        for (int j = i - 3; j <= i; j++)
        {
            P[lol] = P[lol] * 10 + Plol[j] - '0';
        }
    }
    if (i >= 0)
    {
        lol++;
        for (int j = 0; j <= i; j++)
        {
            P[lol] = P[lol] * 10 + Plol[j] - '0';
        }
    }
    P[0] = lol;
    fin.close ();
}

void Initializare_Putere () {
    putere[0] = 1;
    putere[1] = 1;
    for (int i = 1; i <= 333; i++)
    {
        Mul ();
    }
}


int Comp (int B) {
    memset (Putere_Slow_A, 0, sizeof (Putere_Slow_A));
    Putere_Slow_A[0] = 1;
    Putere_Slow_A[1] = 1;
    for (int i = 0; i < B; i++)
    {
            Mul_Mare ();
            if (P[0] < Putere_Slow_A[0]) return 0;
    }
    if (P[0] < Putere_Slow_A[0]) return 0;
    if (P[0] > Putere_Slow_A[0]) return 1;
    for (int i = P[0]; i >= 1; i--)
    {
        if (P[i] < Putere_Slow_A[i]) return 0;
        if (P[i] > Putere_Slow_A[i]) return 1;
    }
    return 2;
}


int B_Search (int B) {
    memcpy (step, putere, sizeof (putere));
    A[0] = 1;
    A[1] = 0;
    for (; step[0] >= 1 && step[1] >= 1; Div())
    {
        Add ();
        if (Comp (B) == 0) Sub ();
    }
    if (Comp (B) == 2)
    {
        fout << A[A[0]];
        for (int i = A[0] - 1; i >= 1; i--)
        {
            if (A[i] < 10) fout << 0;
            if (A[i] < 100) fout << 0;
            if (A[i] < 1000) fout << 0;
            if (A[i] < 10000) fout << 0;
            if (A[i] < 100000) fout << 0;
            if (A[i] < 1000000) fout << 0;
            if (A[i] < 10000000) fout << 0;
            if (A[i] < 100000000) fout << 0;
            fout << A[i];
        }
        fout << "\n" << B;
        fout.close ();
        return 1;
    }
    return 0;
}

int main () {
    Citire ();
    if (P[0] == 1 && P[1] == 1)
    {
        fout << "1\n1";
        fout.close ();
        return 0;
    }
    Initializare_Putere ();
    for (int i = 150; i >= 1; i--)
    {
        if (B_Search (i)) return 0;
    }
}