import java.util.*;
import java.util.concurrent.*;

public class Euler322 {
    static List<Integer> toBaseDigits(long x, int base) {
        List<Integer> digits = new ArrayList<>();
        if (x == 0) {
            digits.add(0);
            return digits;
        }
        while (x > 0) {
            digits.add((int) (x % base));
            x /= base;
        }
        return digits;
    }

    static long countNoCarryPrime(long n, long limit, int p) {
        if (limit == 0)
            return 0;
        long maxValue = limit - 1;
        List<Integer> nDigits = toBaseDigits(n, p);
        List<Integer> xDigits = toBaseDigits(maxValue, p);

        int len = Math.max(nDigits.size(), xDigits.size());
        while (nDigits.size() < len)
            nDigits.add(0);
        while (xDigits.size() < len)
            xDigits.add(0);

        long tight = 1;
        long loose = 0;

        for (int pos = len - 1; pos >= 0; --pos) {
            int allowedMax = p - 1 - nDigits.get(pos);
            int boundDigit = xDigits.get(pos);

            long nextTight = 0;
            long nextLoose = 0;

            if (allowedMax >= 0) {
                nextLoose += loose * (allowedMax + 1);
                for (int d = 0; d <= Math.min(allowedMax, boundDigit); ++d) {
                    if (d < boundDigit) {
                        nextLoose += tight;
                    } else {
                        nextTight += tight;
                    }
                }
            }
            tight = nextTight;
            loose = nextLoose;
        }
        return tight + loose;
    }

    static void generateLowValuesRec(List<Integer> allowedDigits, int pos, int split, long current, long placeValue,
            List<Long> out) {
        if (pos == split) {
            out.add(current);
            return;
        }
        for (int d = 0; d <= allowedDigits.get(pos); ++d) {
            generateLowValuesRec(allowedDigits, pos + 1, split, current + d * placeValue, placeValue * 5L, out);
        }
    }

    static List<Long> generateLowValues(List<Integer> allowedDigits, int split) {
        List<Long> out = new ArrayList<>();
        generateLowValuesRec(allowedDigits, 0, split, 0L, 1L, out);
        return out;
    }

    static class Node {
        int pos;
        boolean tight;
        long value;

        Node(int p, boolean t, long v) {
            pos = p;
            tight = t;
            value = v;
        }
    }

    static List<Long> generateHighValues(List<Integer> allowedDigits, int split, long highBound) {
        List<Integer> boundDigits = toBaseDigits(highBound, 5);
        int len = boundDigits.size();

        List<Integer> highAllowed = new ArrayList<>(Collections.nCopies(len, 4));
        for (int i = 0; i < len; ++i) {
            int originalPos = i + split;
            if (originalPos < allowedDigits.size()) {
                highAllowed.set(i, allowedDigits.get(originalPos));
            }
        }

        long[] pow5 = new long[len + 1];
        pow5[0] = 1L;
        for (int i = 1; i <= len; ++i)
            pow5[i] = pow5[i - 1] * 5L;

        List<Node> stack = new ArrayList<>();
        stack.add(new Node(0, true, 0L));

        List<Long> out = new ArrayList<>();

        while (!stack.isEmpty()) {
            Node node = stack.remove(stack.size() - 1);
            if (node.pos == len) {
                out.add(node.value);
                continue;
            }

            int digitIndex = len - 1 - node.pos;
            int limitDigit = node.tight ? boundDigits.get(digitIndex) : 4;
            int allowedDigit = highAllowed.get(digitIndex);
            int maxDigit = Math.min(limitDigit, allowedDigit);

            for (int d = maxDigit; d >= 0; --d) {
                stack.add(new Node(
                        node.pos + 1,
                        node.tight && (d == limitDigit),
                        node.value + d * pow5[digitIndex]));
            }
        }
        return out;
    }

    static class Worker implements Callable<Long> {
        List<Long> lowValues;
        List<Long> scaledHighValues;
        long n;
        int start, end;

        Worker(List<Long> lows, List<Long> highs, long n, int start, int end) {
            this.lowValues = lows;
            this.scaledHighValues = highs;
            this.n = n;
            this.start = start;
            this.end = end;
        }

        public Long call() {
            long local = 0;
            for (int i = start; i < end; i++) {
                long low = lowValues.get(i);
                for (long scaled : scaledHighValues) {
                    long x = low + scaled;
                    if ((x & n) == 0) {
                        local++;
                    }
                }
            }
            return local;
        }
    }

    static long countOverlapCoprime10(long n, long limit) throws Exception {
        if (limit == 0)
            return 0;
        long maxValue = limit - 1;
        List<Integer> nDigits = toBaseDigits(n, 5);
        List<Integer> xDigits = toBaseDigits(maxValue, 5);

        int len = Math.max(nDigits.size(), xDigits.size());
        while (nDigits.size() < len)
            nDigits.add(0);
        while (xDigits.size() < len)
            xDigits.add(0);

        List<Integer> allowedDigits = new ArrayList<>(Collections.nCopies(len, 4));
        for (int i = 0; i < len; ++i) {
            allowedDigits.set(i, 4 - nDigits.get(i));
        }

        int split = 0;
        while (split < len && xDigits.get(split).equals(allowedDigits.get(split))) {
            split++;
        }

        long step = 1;
        for (int i = 0; i < split; i++)
            step *= 5L;
        long highBound = maxValue / step;

        List<Long> lowValues = generateLowValues(allowedDigits, split);
        List<Long> highValues = generateHighValues(allowedDigits, split, highBound);

        List<Long> scaledHighValues = new ArrayList<>();
        for (long h : highValues)
            scaledHighValues.add(h * step);

        int threads = Runtime.getRuntime().availableProcessors();
        ExecutorService ex = Executors.newFixedThreadPool(threads);
        List<Future<Long>> futures = new ArrayList<>();

        int batchSize = Math.max(1, lowValues.size() / threads);
        for (int i = 0; i < lowValues.size(); i += batchSize) {
            int end = Math.min(lowValues.size(), i + batchSize);
            futures.add(ex.submit(new Worker(lowValues, scaledHighValues, n, i, end)));
        }

        long total = 0;
        for (Future<Long> f : futures) {
            total += f.get();
        }
        ex.shutdown();

        return total;
    }

    static long solveT(long m, long n) throws Exception {
        long interval = m - n;
        long notDiv2 = countNoCarryPrime(n, interval, 2);
        long notDiv5 = countNoCarryPrime(n, interval, 5);
        long coprime10 = countOverlapCoprime10(n, interval);

        return interval - notDiv2 - notDiv5 + coprime10;
    }

    public static String solve() {
        try {
            long m = 1000000000000000000L;
            long n = 1000000000000L - 10L;
            return String.valueOf(solveT(m, n));
        } catch (Exception e) {
            return "Error";
        }
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}