import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;

public class Euler464 {

    static class Fenwick {
        int[] bit;

        Fenwick(int n) {
            bit = new int[n + 1];
        }

        void add(int idx, int delta) {
            while (idx < bit.length) {
                bit[idx] += delta;
                idx += idx & -idx;
            }
        }

        int sum(int idx) {
            int result = 0;
            while (idx > 0) {
                result += bit[idx];
                idx -= idx & -idx;
            }
            return result;
        }
    }

    static byte[] mobiusValues(int n) {
        int[] lp = new int[n + 1];
        List<Integer> primes = new ArrayList<>(n / 10);
        byte[] mu = new byte[n + 1];
        mu[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (lp[i] == 0) {
                lp[i] = i;
                primes.add(i);
                mu[i] = -1;
            }
            for (int p : primes) {
                long x = (long) p * i;
                if (x > n || p > lp[i])
                    break;
                lp[(int) x] = p;
                if (p == lp[i]) {
                    mu[(int) x] = 0;
                    break;
                }
                mu[(int) x] = (byte) -mu[i];
            }
        }
        return mu;
    }

    static long countPositiveWeightedSegments(byte[] mu, int weightPos, int weightNeg) {
        int n = mu.length - 1;
        int[] prefix = new int[n + 1];

        int cur = 0;
        int minPrefix = 0;
        int maxPrefix = 0;

        for (int i = 1; i <= n; i++) {
            int m = mu[i];
            if (m == 1)
                cur += weightPos;
            else if (m == -1)
                cur += weightNeg;
            prefix[i] = cur;
            if (cur < minPrefix)
                minPrefix = cur;
            if (cur > maxPrefix)
                maxPrefix = cur;
        }

        long span = (long) maxPrefix - minPrefix + 1;
        long DENSE_LIMIT = 50000000L;
        long positives = 0;

        if (span <= DENSE_LIMIT) {
            Fenwick bit = new Fenwick((int) span + 2);
            for (int i = 0; i <= n; i++) {
                int idx = prefix[i] - minPrefix + 1;
                positives += bit.sum(idx - 1);
                bit.add(idx, 1);
            }
            return positives;
        }

        int[] coords = prefix.clone();
        Arrays.sort(coords);

        int uniqueCount = 0;
        if (coords.length > 0) {
            uniqueCount = 1;
            for (int i = 1; i < coords.length; i++) {
                if (coords[i] != coords[i - 1]) {
                    coords[uniqueCount++] = coords[i];
                }
            }
        }

        Fenwick bit = new Fenwick(uniqueCount + 2);
        for (int i = 0; i <= n; i++) {
            int v = prefix[i];
            int idx = Arrays.binarySearch(coords, 0, uniqueCount, v) + 1;
            positives += bit.sum(idx - 1);
            bit.add(idx, 1);
        }

        return positives;
    }

    public static String solve() {
        int n = 20000000;
        byte[] mu = mobiusValues(n);
        long totalPairs = (long) n * (n + 1) / 2L;

        long badA = countPositiveWeightedSegments(mu, 99, -100);
        long badB = countPositiveWeightedSegments(mu, -100, 99);

        return Long.toString(totalPairs - badA - badB);
    }

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