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
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class fib {

    private static List<Long>[] idx;

    private static class Fibo {
        private BigInteger index;
        private BigInteger value;

        public Fibo(BigInteger index, BigInteger value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public String toString() {
            String s = value.toString();
            String shorter = (s.length() < 40) ? s : s.substring(0, 10) + "..." + s.substring(s.length() - 20) + " (" + s.length() + " digits)";
            return "Fibo [index: " + index + ", value: " + shorter + "]";
        }
    }

    public static void main(String[] args) {
        generate();

        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            String input = cin.nextLine();

            if (input.length() < 2) {
                input = "0" + input;
            }

            doWork(input);
        }
    }

    private static void doWork(String input) {
        int v = Integer.valueOf(input.substring(input.length() - 2));
        List<Long> indices = idx[v];

        BigInteger mod = pow10n(input.length());

        for (int n = 3; n <= input.length(); n++) {
            HashSet<Fibo> check = check(input.substring(input.length() - n), indices);
            if (check.isEmpty()) {
                System.out.println("NIE");
                return;
            }

            indices = new ArrayList<>();
            for (Fibo fibo : check) {
                if (fibo.value.mod(mod).toString().equals(input)) {
                    System.out.println(fibo.index);
                    return;
                }
                indices.add(fibo.index.longValue());
            }
        }

        System.out.println(indices.get(0));
    }

    private static HashSet<Fibo> check(String input, List<Long> integers) {
        HashSet<Fibo> fibos = new HashSet<>();
        long v = Long.valueOf(input);

        int power = input.length();
        BigInteger mod = pow10n(power);

        BigInteger period = pisanoPeriod(power - 1);
        BigInteger limit = pisanoPeriod(power);

        for (Long index : integers) {
            int b = 0;
            while (true) {
                BigInteger c = BigInteger.valueOf(index).add(period.multiply(BigInteger.valueOf(b++)));
                if (c.compareTo(limit) > 0) {
                    break;
                }

                BigInteger x = genFib(c, power);
                if (x.mod(mod).longValue() == v) {
                    fibos.add(new Fibo(c, x));
                }

            }

        }
        return fibos;
    }

    private static BigInteger pisanoPeriod(int n) {
        if (n == 1) {
            return BigInteger.valueOf(60);
        }

        if (n == 2) {
            return BigInteger.valueOf(300);
        }

        return pow10n(n - 1).multiply(BigInteger.valueOf(15));
    }


    public static BigInteger genFib(BigInteger n, int exponent) {
        BigInteger matrix[][] = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}};
        if (n.equals(BigInteger.ZERO)) {
            return BigInteger.ZERO;
        } else {
            MatrixUtils.powerMod10n(matrix, n.subtract(BigInteger.ONE), exponent);
            return matrix[0][0].mod(pow10n(exponent));
        }
    }

    static class MatrixUtils {

        private static void powerMod10n(BigInteger matrix[][], BigInteger n, int exponent) {
            if (n.equals(BigInteger.ZERO) || n.equals(BigInteger.ONE)) {
                return;
            }

            BigInteger identity[][] = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}};
            powerMod10n(matrix, n.divide(BigInteger.valueOf(2)), exponent);
            multiplyMod10n(matrix, matrix, exponent);

            if (!n.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
                multiplyMod10n(matrix, identity, exponent);
            }
        }

        private static void multiplyMod10n(BigInteger matrix1[][], BigInteger matrix2[][], int exponent) {
            BigInteger m = pow10n(exponent);
            BigInteger a = (matrix1[0][0].multiply(matrix2[0][0]))
                    .add(matrix1[0][1].multiply(matrix2[1][0]));
            BigInteger b = (matrix1[0][0].multiply(matrix2[0][1]))
                    .add(matrix1[0][1].multiply(matrix2[1][1]));
            BigInteger c = (matrix1[1][0].multiply(matrix2[0][0]))
                    .add(matrix1[1][1].multiply(matrix2[1][0]));
            BigInteger d = (matrix1[1][0].multiply(matrix2[0][1]))
                    .add(matrix1[1][1].multiply(matrix2[1][1]));
            matrix1[0][0] = a.mod(m);
            matrix1[0][1] = b.mod(m);
            matrix1[1][0] = c.mod(m);
            matrix1[1][1] = d.mod(m);
        }
    }

    private static BigInteger pow10n(int exponent) {
        return BigInteger.valueOf(10).pow(exponent);
    }

    private static void generate() {
        int a = 0;
        int b = 1;
        long i = 2;

        int mod = (int) Math.pow(10, 2);
        int mod2 = (int) Math.pow(10, 3);

        ArrayList<Integer> seq = new ArrayList<>();
        seq.add(0);
        seq.add(1);
        int offset = 0;

        idx = new List[100];
        idx[0] = new ArrayList<>();
        idx[1] = new ArrayList<>();
        idx[0].add(0L);
        idx[1].add(1L);

        while (true) {
            int c = (a + b) % mod;

            if (idx[c] == null) {
                idx[c] = new ArrayList<>();
            }
            idx[c].add(i);
            i++;

            if (c == seq.get(offset)) {
                offset++;
                if (offset == 2) {
                    return;
                }
            } else {
                offset = 0;
            }

            a = b;
            b = c % mod2;
        }
    }

}