public class Euler104 {
    static boolean isPan(String s) {
        if (s.length() != 9)
            return false;
        boolean[] seen = new boolean[10];
        for (char c : s.toCharArray()) {
            int d = c - '0';
            if (d == 0 || seen[d])
                return false;
            seen[d] = true;
        }
        return true;
    }

    public static void main(String[] args) {
        long MOD = 1000000000L, a = 1, b = 1;
        double logPhi = Math.log10((1 + Math.sqrt(5)) / 2), logSqrt5 = Math.log10(5) / 2;
        for (int n = 3;; n++) {
            long c = (a + b) % MOD;
            a = b;
            b = c;
            String tail = String.format("%09d", b);
            if (!isPan(tail))
                continue;
            double logFn = n * logPhi - logSqrt5;
            double frac = logFn - Math.floor(logFn);
            String lead = Long.toString((long) Math.pow(10, frac + 8)).substring(0, 9);
            if (isPan(lead)) {
                System.out.println(n);
                return;
            }
        }
    }
}