public class Euler182 {
    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        int p = 1009, q = 3643, phi = (p - 1) * (q - 1);
        long best = -1, sum = 0;
        for (int e = 2; e < phi; e++) {
            if (gcd(e, phi) != 1)
                continue;
            long cnt = (long) (gcd(e - 1, p - 1) + 1) * (gcd(e - 1, q - 1) + 1);
            if (best < 0 || cnt < best) {
                best = cnt;
                sum = e;
            } else if (cnt == best)
                sum += e;
        }
        System.out.println(sum);
    }
}