import java.util.ArrayList;

public class Euler871 {

    static int pathMax(int[] w, int l, int r) {
        if (l > r)
            return 0;
        int a = 0, b = 0;
        for (int i = l; i <= r; ++i) {
            int c = Math.max(b, a + w[i]);
            a = b;
            b = c;
        }
        return b;
    }

    static int DValue(int n) {
        int[] to = new int[n];
        int[] indeg = new int[n];
        ArrayList<Integer>[] preds = new ArrayList[n];
        for (int i = 0; i < n; ++i)
            preds[i] = new ArrayList<>();

        for (int x = 0; x < n; ++x) {
            long y = x;
            int v = (int) (((y * y % n) * y + y + 1) % n);
            to[x] = v;
            indeg[v]++;
            preds[v].add(x);
        }

        int[] q = new int[n];
        int head = 0, tail = 0;
        for (int i = 0; i < n; ++i) {
            if (indeg[i] == 0) {
                q[tail++] = i;
            }
        }

        int[] order = new int[n];
        int orderCount = 0;

        while (head < tail) {
            int u = q[head++];
            order[orderCount++] = u;

            int v = to[u];
            indeg[v]--;
            if (indeg[v] == 0) {
                q[tail++] = v;
            }
        }

        int[] dp0 = new int[n];
        int[] dp1 = new int[n];

        for (int t = 0; t < orderCount; ++t) {
            int u = order[t];
            int base = 0;
            int best = 0;

            for (int c : preds[u]) {
                if (indeg[c] == 0) {
                    base += dp0[c];
                    best = Math.max(best, dp1[c] - dp0[c]);
                }
            }

            dp0[u] = base + Math.max(0, best);
            dp1[u] = base + 1;
        }

        boolean[] vis = new boolean[n];
        int ans = 0;

        for (int s = 0; s < n; ++s) {
            if (indeg[s] == 0 || vis[s])
                continue;

            ArrayList<Integer> cyc = new ArrayList<>();
            int u = s;
            while (!vis[u]) {
                vis[u] = true;
                cyc.add(u);
                u = to[u];
            }

            int k = cyc.size();
            int[] baseArr = new int[k];
            int[] gain = new int[k];

            for (int i = 0; i < k; ++i) {
                int x = cyc.get(i);
                int b = 0;
                int g = 0;

                for (int c : preds[x]) {
                    if (indeg[c] == 0) {
                        b += dp0[c];
                        g = Math.max(g, dp1[c] - dp0[c]);
                    }
                }

                baseArr[i] = b;
                gain[i] = Math.max(0, g);
            }

            int comp = 0;
            for (int i = 0; i < k; ++i) {
                comp += baseArr[i] + gain[i];
            }

            if (k == 1) {
                ans += comp;
                continue;
            }

            int[] w = new int[k];
            for (int i = 0; i < k; ++i) {
                int j = (i + 1 == k ? 0 : i + 1);
                w[i] = 1 - gain[i] - gain[j];
            }

            int bestA = pathMax(w, 1, k - 1);
            int bestB = w[0] + pathMax(w, 2, k - 2);
            int best = Math.max(0, Math.max(bestA, bestB));

            ans += comp + best;
        }

        return ans;
    }

    public static String solve() {
        int sum = 0;
        for (int i = 1; i <= 100; ++i) {
            sum += DValue(100000 + i);
        }
        return Integer.toString(sum);
    }

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