1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>

using namespace std;

bool comp(int *A, int *B, int n) {
    for(int i = 0; i < n; i++)
        if(A[i] != B[i])
            return false;
    return true;
}

void copy(int *dst, int *src, int n) {
    for(int i = 0; i < n; i++)
        dst[i] = src[i];
}

void add(int *dst, int *a, int *b, int n) {
    for(int i = 0; i < n; i++)
        dst[i] = a[i] + b[i];
    for(int i = n-1; i >= 0; i--) {
        if(dst[i] > 9 && i != 0)
            dst[i-1] += dst[i]/10;
        dst[i] %= 10;
    }
}

int main() {
    ios_base::sync_with_stdio(0);

    string c;
    cin >> c;

    if(c == "1") {
        cout << 1 << endl;
        return 0;
    }

    int L = c.length();
    int A[L];
    int B[L];
    int X[L];
    int C[L];
    int I[L];

    for(int i = 0; i < L; i++) {
        A[i] = 0;
        B[i] = 0;
        X[i] = 0;
        C[i] = c[i]-'0';
        I[i] = 0;
    }
    A[L-1] = 1;
    B[L-1] = 1;
    I[L-1] = 1;

    const double long MAX = 5000000;
    double long k = 2;
    while(comp(X, C, L) == false && k < MAX) {
        add(X, A, B, L);
        copy(A, B, L);
        copy(B, X, L);
        k++;
        if(comp(A, I, L) == true && comp(B, I, L) == true)
            k = MAX+1;
    }

    if(k > MAX)
        cout << "NIE" << endl;
    else
        cout << k << endl;

    return 0;
}