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

public class Euler693 {
    static List<Integer> initialActiveAfterFirstStep(int x) {
        if (x <= 2)
            return new ArrayList<>();

        byte[] seen = new byte[x];
        List<Integer> active = new ArrayList<>();

        long mod = x;
        long limit = mod / 2;

        long y = 2;
        long sq = (y * y) % mod;
        long delta = 2 * y + 1;

        while (y <= limit) {
            if (sq > 1 && seen[(int) sq] == 0) {
                seen[(int) sq] = 1;
                active.add((int) sq);
            }
            sq += delta;
            if (sq >= mod) {
                sq -= mod;
                if (sq >= mod)
                    sq -= mod;
            }
            delta += 2;
            y++;
        }
        return active;
    }

    static List<Integer> stepActiveDense(List<Integer> active, int mod) {
        byte[] seen = new byte[mod];
        List<Integer> next = new ArrayList<>();

        for (int a : active) {
            long v = ((long) a * a) % mod;
            if (v > 1 && seen[(int) v] == 0) {
                seen[(int) v] = 1;
                next.add((int) v);
            }
        }
        return next;
    }

    static List<Integer> stepActiveSparse(List<Integer> active, int mod) {
        HashSet<Integer> nextSet = new HashSet<>();
        for (int a : active) {
            long v = ((long) a * a) % mod;
            if (v > 1) {
                nextSet.add((int) v);
            }
        }
        return new ArrayList<>(nextSet);
    }

    static int gValue(int x) {
        if (x < 2)
            return 0;
        if (x == 2)
            return 1;

        List<Integer> active = initialActiveAfterFirstStep(x);
        int length = 2;
        int mod = x + 1;

        int denseThreshold = 120000;

        while (active.size() > 1) {
            if (active.size() >= denseThreshold) {
                active = stepActiveDense(active, mod);
            } else {
                active = stepActiveSparse(active, mod);
            }
            length++;
            mod++;
            if (active.isEmpty())
                return length;
        }

        if (active.isEmpty())
            return length;

        long value = active.get(0);
        while (value > 1) {
            value = (value * value) % mod;
            length++;
            mod++;
        }

        return length;
    }

    static int snappedGridStep(int rawStep) {
        if (rawStep <= 1)
            return 1;
        int power = (int) Math.floor(Math.log10(rawStep));
        int base = 1;
        for (int i = 0; i < power; i++)
            base *= 10;

        int[] mults = { 1, 2, 5, 10 };
        for (int m : mults) {
            if ((long) m * base >= rawStep) {
                return m * base;
            }
        }
        return rawStep;
    }

    static class Interval implements Comparable<Interval> {
        int upperBound, left, right, gRight;

        public Interval(int ub, int l, int r, int gr) {
            this.upperBound = ub;
            this.left = l;
            this.right = r;
            this.gRight = gr;
        }

        @Override
        public int compareTo(Interval o) {
            return Integer.compare(o.upperBound, this.upperBound); // descending
        }
    }

    public static String solve() {
        int n = 3000000;
        int targetPoints = 16;
        int pointsCount = Math.max(2, targetPoints);
        int rawStep = Math.max(1, (n - 2) / (pointsCount - 1));
        int gridStep = snappedGridStep(rawStep);

        List<Integer> points = new ArrayList<>();
        for (long x = 2; x <= n; x += gridStep) {
            points.add((int) x);
            if (x > (long) n - gridStep)
                break;
        }
        if (points.get(points.size() - 1) != n) {
            points.add(n);
        }

        int threads = Runtime.getRuntime().availableProcessors();
        if (threads < 1)
            threads = 1;

        int[] gPoints = new int[points.size()];
        ExecutorService pool = Executors.newFixedThreadPool(threads);
        List<Future<?>> futures = new ArrayList<>();

        for (int i = 0; i < points.size(); i++) {
            final int idx = i;
            futures.add(pool.submit(() -> {
                gPoints[idx] = gValue(points.get(idx));
            }));
        }

        for (Future<?> f : futures) {
            try {
                f.get();
            } catch (Exception e) {
            }
        }
        pool.shutdown();

        ConcurrentHashMap<Integer, Integer> cache = new ConcurrentHashMap<>();
        int best = 0;
        for (int i = 0; i < points.size(); i++) {
            cache.put(points.get(i), gPoints[i]);
            if (gPoints[i] > best)
                best = gPoints[i];
        }

        PriorityQueue<Interval> pq = new PriorityQueue<>();
        for (int i = 1; i < points.size(); i++) {
            int left = points.get(i - 1);
            int right = points.get(i);
            int gRight = gPoints[i];
            int upperBound = gRight + (right - left);
            pq.add(new Interval(upperBound, left, right, gRight));
        }

        while (!pq.isEmpty()) {
            Interval top = pq.poll();
            if (top.upperBound <= best)
                break;

            if (top.right - top.left <= 1)
                continue;

            int mid = top.left + (top.right - top.left) / 2;
            int gMid = cache.computeIfAbsent(mid, m -> gValue(m));
            if (gMid > best)
                best = gMid;

            if (mid - top.left > 1) {
                int ubLeft = gMid + (mid - top.left);
                if (ubLeft > best)
                    pq.add(new Interval(ubLeft, top.left, mid, gMid));
            }
            if (top.right - mid > 1) {
                int ubRight = top.gRight + (top.right - mid);
                if (ubRight > best)
                    pq.add(new Interval(ubRight, mid, top.right, top.gRight));
            }
        }

        return Integer.toString(best);
    }

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