public class Euler186 {
    static int[] parent, size;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    static void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return;
        if (size[a] < size[b]) {
            int t = a;
            a = b;
            b = t;
        }
        parent[b] = a;
        size[a] += size[b];
    }

    public static void main(String[] args) {
        int N = 1000000, pm = 524287;
        parent = new int[N];
        size = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            size[i] = 1;
        }
        int[] s = new int[56];
        for (int k = 1; k <= 55; k++)
            s[k] = (int) ((100003L - 200003L * k + 300007L * k * k * k) % 1000000);
        int[] buf = new int[55];
        for (int i = 0; i < 55; i++)
            buf[i] = s[i + 1];
        int idx = 0;
        int bufLen = 55;
        int target = N * 99 / 100;
        int succ = 0;
        java.util.ArrayList<Integer> bufList = new java.util.ArrayList<>();
        for (int b : buf)
            bufList.add(b);
        while (size[find(pm)] < target) {
            int caller, called;
            if (idx < bufList.size()) {
                caller = bufList.get(idx);
            } else {
                bufList.add((bufList.get(bufList.size() - 24) + bufList.get(bufList.size() - 55)) % 1000000);
                caller = bufList.get(idx);
            }
            idx++;
            if (idx - 1 < bufList.size() - 1 && idx < bufList.size()) {
                called = bufList.get(idx);
            } else {
                bufList.add((bufList.get(bufList.size() - 24) + bufList.get(bufList.size() - 55)) % 1000000);
                called = bufList.get(idx);
            }
            idx++;
            if (caller == called)
                continue;
            succ++;
            unite(caller, called);
        }
        System.out.println(succ);
    }
}