import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Euler543 {
    static long isqrt(long n) {
        if (n == 0)
            return 0;
        long x = (long) Math.sqrt((double) n);
        while ((x + 1) <= n / (x + 1))
            x++;
        while (x > 0 && x > n / x)
            x--;
        return x;
    }

    static long icbrt(long n) {
        if (n == 0)
            return 0;
        long x = (long) Math.cbrt((double) n);
        while ((x + 1) <= n / ((x + 1) * (x + 1)))
            x++;
        while (x > 0 && x > n / (x * x))
            x--;
        return x;
    }

    static long iroot4(long n) {
        if (n == 0)
            return 0;
        long r = (long) Math.sqrt(Math.sqrt((double) n));
        while (Math.pow(r + 1, 4) <= n)
            r++;
        while (r > 0 && Math.pow(r, 4) > n)
            r--;
        return r;
    }

    static class PrimeCounter {
        int sieveLimit;
        List<Integer> primes;
        long[] piSmall;
        Map<Long, Long> piCache;
        Map<Long, Long> phiCache;

        PrimeCounter(int sieveLimit) {
            this.sieveLimit = sieveLimit;
            boolean[] isComp = new boolean[sieveLimit + 1];
            piSmall = new long[sieveLimit + 1];
            primes = new ArrayList<>();

            for (int i = 2; i <= sieveLimit; i++) {
                if (!isComp[i]) {
                    primes.add(i);
                    if (i <= sieveLimit / i) {
                        for (int j = i * i; j <= sieveLimit; j += i) {
                            isComp[j] = true;
                        }
                    }
                }
                piSmall[i] = piSmall[i - 1] + (!isComp[i] ? 1 : 0);
            }
            piCache = new HashMap<>();
            phiCache = new HashMap<>();
        }

        long pi(long n) {
            if (n <= sieveLimit) {
                return piSmall[(int) n];
            }
            Long cached = piCache.get(n);
            if (cached != null)
                return cached;

            long a = pi(iroot4(n));
            long b = pi(isqrt(n));
            long c = pi(icbrt(n));

            long sum = phi(n, (int) a) + (b + a - 2) * (b - a + 1) / 2;

            for (long i = a + 1; i <= b; i++) {
                long w = n / primes.get((int) (i - 1));
                sum -= pi(w);
                if (i <= c) {
                    long lim = pi(isqrt(w));
                    for (long j = i; j <= lim; j++) {
                        long pj = primes.get((int) (j - 1));
                        sum -= pi(w / pj) - (j - 1);
                    }
                }
            }

            piCache.put(n, sum);
            return sum;
        }

        long phi(long x, int s) {
            if (s == 0)
                return x;
            if (s == 1)
                return x - x / 2;
            if (s == 2)
                return x - x / 2 - x / 3 + x / 6;
            if (s == 3)
                return x - x / 2 - x / 3 - x / 5 + x / 6 + x / 10 + x / 15 - x / 30;
            if (x <= sieveLimit && primes.get(s - 1) >= x)
                return 1;

            long key = (x << 6) ^ s;
            Long cached = phiCache.get(key);
            if (cached != null)
                return cached;

            long ps = primes.get(s - 1);
            long ans = phi(x, s - 1) - phi(x / ps, s - 1);
            phiCache.put(key, ans);
            return ans;
        }
    }

    static long S_of(long n, PrimeCounter pc) {
        long pi_n = pc.pi(n);
        long pi_n_minus2 = n >= 2 ? pc.pi(n - 2) : 0;

        long m = n / 2;
        long even_2prime = m >= 2 ? (m - 1) : 0;
        long odd_2prime = pi_n_minus2 >= 1 ? (pi_n_minus2 - 1) : 0;

        long sum_even_kge3 = m >= 3 ? (m - 1) * (m - 2) / 2 : 0;
        long m2 = n >= 1 ? (n - 1) / 2 : 0;
        long sum_odd_kge3 = m2 >= 3 ? (m2 - 1) * (m2 - 2) / 2 : 0;

        return pi_n + even_2prime + odd_2prime + sum_even_kge3 + sum_odd_kge3;
    }

    public static String solve() {
        PrimeCounter pc = new PrimeCounter(5000000);
        long f0 = 0;
        long f1 = 1;
        long total = 0;
        for (int k = 2; k <= 44; k++) {
            long f = f0 + f1;
            f0 = f1;
            f1 = f;
            if (k >= 3) {
                total += S_of(f, pc);
            }
        }
        return Long.toString(total);
    }

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