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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class fib {
    public static final BigInteger MOD = new BigInteger("1000000000000000000");
    public static final BigInteger ZERO = BigInteger.ZERO;
    public static final BigInteger ONE = BigInteger.ONE;
    public static final BigInteger FIVE = new BigInteger("5");
    public static final BigInteger TEN = new BigInteger("10");
    public static final BigInteger FIRST_19_DIGITS_FIB = new BigInteger("88");

    private static Map<BigInteger, BigInteger> fibs = new HashMap<>();

    // F(2n-1) = F(n-1)^2 + F(n)^2
    // F(2n) = ( 2 F(n-1) + F(n) ) F(n)
    private static String fibonacci(BigInteger fi) {
        fibs.clear();
        fibs.put(ZERO, ZERO);
        fibs.put(ONE, ONE);
        BigInteger fib2 = fib2(fi);
        if (fi.compareTo(FIRST_19_DIGITS_FIB) == -1) {
            return fib2.toString();
        }
        String fib2string = fib2.toString();
        return ("000000000000000000" + fib2string).substring(fib2string.length());
    }

    private static BigInteger fib2(BigInteger fi) {
        if (fibs.containsKey(fi)) {
            return fibs.get(fi);
        }
        BigInteger value;
        if (fi.testBit(0)) {
            BigInteger n = fi.add(ONE).shiftRight(1);
            BigInteger fibn = fib2(n);
            BigInteger fibn2 = fibn.multiply(fibn);
            BigInteger fibn1 = fib2(n.subtract(ONE));
            BigInteger fibn12 = fibn1.multiply(fibn1);
            value = fibn2.add(fibn12);
        } else {
            BigInteger n = fi.shiftRight(1);
            BigInteger fibn = fib2(n);
            value = fib2(n.subtract(ONE)).shiftLeft(1).add(fibn).multiply(fibn);
        }
        value = value.mod(MOD);
        fibs.put(fi, value);
        return value;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String numberString = in.readLine();
        in.close();

        List<BigInteger> suspects = new ArrayList<>();
        char lastChar = numberString.charAt(numberString.length() - 1);
        for (Integer fi = 0; fi < 60; fi++) {
            BigInteger fibi = new BigInteger(fi.toString());
            String f = fibonacci(fibi);
            char fLastChar = f.charAt(f.length() - 1);
            if (lastChar == fLastChar) {
                suspects.add(fibi);
            }
        }

        BigInteger cycle = new BigInteger("60");
        for (int i = 2; i <= numberString.length(); i++) {
            char neededChar = numberString.charAt(numberString.length() - i);
            List<BigInteger> newSuspects = new ArrayList<>();
            for (BigInteger fibi : suspects) {
                BigInteger next = fibi;
                int maxA = i < 4 ? 5 : 10;
                for (int a = 0; a < maxA; a++) {
                    String f = fibonacci(next);
                    if (f.length() >= i) {
                        char fChar = f.charAt(f.length() - i);
                        if (neededChar == fChar) {
                            newSuspects.add(next);
                        }
                    } else {
                        newSuspects.add(next);
                    }
                    next = next.add(cycle);
                }
            }
            if (i < 4)
                cycle = cycle.multiply(FIVE);
            else
                cycle = cycle.multiply(TEN);
            suspects = newSuspects;
        }

        BigInteger answer = null;
        for (BigInteger fibi : suspects) {
            if (fibonacci(fibi).endsWith(numberString)) {
                answer = fibi;
                break;
            }
        }

        if (answer == null) {
            System.out.println("NIE");
        } else {
            System.out.println(answer);
        }
    }

}