public class Euler604 {

    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    static boolean hasBalancedTripleEven2(long s) {
        long n = s / 2;
        if (n < 7)
            return false;
        long LIM = 2000;
        for (long d1 = 2; d1 <= LIM && d1 < n; d1 += 2) {
            if (gcd(d1, n) != 1)
                continue;
            for (long d2 = d1 + 2; d2 <= LIM && d1 + d2 < n; d2 += 2) {
                if (gcd(d2, n) != 1)
                    continue;
                if (gcd(d1 + d2, n) != 1)
                    continue;
                return true;
            }
        }
        return false;
    }

    static int upperBound(long[] a, long key) {
        int low = 0;
        int high = a.length - 1;
        int maxLessOrEqual = -1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            if (a[mid] <= key) {
                maxLessOrEqual = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return maxLessOrEqual == -1 ? 0 : maxLessOrEqual + 1;
    }

    static long F(long N, long[] prefPhi, long[] prefCost) {
        long target = 2 * N;
        int it = upperBound(prefCost, target);
        int m = (it == 0) ? 0 : it - 1;

        long baseCnt = (m >= 2) ? prefPhi[m] : 0;
        long baseCost = (m >= 2) ? prefCost[m] : 0;

        long slack = target - baseCost;
        long s = m + 1;
        long t = (s > 0) ? (slack / s) : 0;
        long r = (s > 0) ? (slack % s) : 0;

        long segments = baseCnt + t;

        if (r == 0 && (t % 2 != 0) && t > 0) {
            boolean ok = false;
            if (t == 1) {
                ok = false;
            } else if (s % 4 == 0) {
                ok = false;
            } else if (s % 4 == 2) {
                ok = hasBalancedTripleEven2(s);
            }
            if (!ok)
                segments--;
        }

        return segments + 1;
    }

    public static String solve() {
        long N_max = 1000000000000000000L;
        long target_max = 2 * N_max;
        int limit = 3000000;
        long[] prefPhi;
        long[] prefCost;

        while (true) {
            int[] phi = new int[limit + 1];
            for (int i = 0; i <= limit; i++)
                phi[i] = i;
            for (int p = 2; p <= limit; p++) {
                if (phi[p] != p)
                    continue;
                for (int j = p; j <= limit; j += p) {
                    phi[j] -= phi[j] / p;
                }
            }

            prefPhi = new long[limit + 1];
            prefCost = new long[limit + 1];

            for (int i = 2; i <= limit; i++) {
                prefPhi[i] = prefPhi[i - 1] + phi[i];
                prefCost[i] = prefCost[i - 1] + (long) i * phi[i];
            }

            if (prefCost[limit] >= target_max)
                break;
            limit = (int) (limit * 1.4) + 1000;
        }

        return Long.toString(F(N_max, prefPhi, prefCost));
    }

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