import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicInteger;

public class Euler986 {
    private static final double[][] COEF = {
            {0.17656501777829126, 0.35981185819773187, -9.093343254260652, 128.0591554042931},
            {0.17791093179771922, -0.02526258663290543, 17.778074509864577, -228.639325004742},
            {0.17688473006194433, 0.30195121097992167, -8.649989398001244, 159.32792700127638},
            {0.1774911030303856, 0.09144288721929997, 9.76665768770627, -161.46727161611716},
            {0.17665123701842447, 0.37639947984877686, -14.382073443985455, 264.68150347640244},
            {0.17652781023196232, 0.37645445228054497, -10.389054848768398, 121.34965708864206},
            {0.17725060801487988, 0.15363937288855242, 7.49278183636027, -167.17442628344003},
            {0.17658285799047665, 0.3729423126656912, -11.25711787747357, 179.7243004469314},
    };

    private static boolean extinctForK(int c, int d, long k) {
        if (k == 0) {
            return true;
        }

        int s = c + d;
        long[] window = new long[s];
        window[s - 1] = k;

        int zeroCount = s - 1;
        int head = 0;
        int tap = s - d;
        long steps = 0;

        while (true) {
            long old = window[head];
            long next = (window[head] + window[tap]) >>> 1;
            window[head] = next;

            if (old != 0) {
                if (next == 0) {
                    zeroCount++;
                }
            } else if (next != 0) {
                zeroCount--;
            }

            head++;
            if (head == s) {
                head = 0;
            }
            tap++;
            if (tap == s) {
                tap = 0;
            }

            steps++;
            if ((steps & 63L) == 0L) {
                if (zeroCount == s) {
                    return true;
                }
                if (zeroCount == 0) {
                    return false;
                }
            }
        }
    }

    private static boolean extinctForKC1(int n, long k) {
        if (k == 0) {
            return true;
        }

        int s = n + 1;
        long[] window = new long[s];
        window[s - 1] = k;

        int zeroCount = s - 1;
        while (true) {
            for (int i = 0; i < s; i++) {
                int j = i + 1;
                if (j == s) {
                    j = 0;
                }

                long old = window[i];
                long next = (window[i] + window[j]) >>> 1;
                window[i] = next;

                if (old != 0) {
                    if (next == 0) {
                        zeroCount++;
                    }
                } else if (next != 0) {
                    zeroCount--;
                }
            }

            if (zeroCount == s) {
                return true;
            }
            if (zeroCount == 0) {
                return false;
            }
        }
    }

    private static long computeK(int c, int d) {
        long lo = 0;
        long hi = 1;

        while (extinctForK(c, d, hi)) {
            lo = hi;
            hi <<= 1;
        }

        while (lo + 1 < hi) {
            long mid = lo + ((hi - lo) >>> 1);
            if (extinctForK(c, d, mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }

        return lo;
    }

    private static long estimateK1(int n) {
        double[] c = COEF[n & 7];
        double x = n;
        double est = ((c[0] * x + c[1]) * x + c[2]) * x + c[3];
        if (est <= 0.0) {
            return 0;
        }
        return Math.round(est);
    }

    private static long computeK1FromEstimate(int n) {
        long guess = estimateK1(n);

        long lo = guess > 2048L ? guess - 2048L : 0L;
        long hi = guess + 2048L;

        while (lo > 0 && !extinctForKC1(n, lo)) {
            hi = lo;
            lo >>>= 1;
        }

        while (extinctForKC1(n, hi)) {
            lo = hi;
            hi <<= 1;
        }

        while (lo + 1 < hi) {
            long mid = lo + ((hi - lo) >>> 1);
            if (extinctForKC1(n, mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }

        return lo;
    }

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

    private static long gValue(int c, int d, long[] kD1, long[] k1) {
        long g = gcd(c, d);
        int rc = (int) (c / g);
        int rd = (int) (d / g);

        long k;
        if (rd == 1) {
            k = kD1[rc];
        } else {
            k = k1[rd + (rc - 1) / 2];
        }
        return 2L * k + 1L;
    }

    private static void require(boolean condition, String message) {
        if (!condition) {
            throw new IllegalStateException(message);
        }
    }

    public static String solve() {
        long[] k1 = new long[240];
        long[] kD1 = new long[161];

        AtomicInteger nextN = new AtomicInteger(1);
        int cpuCount = Runtime.getRuntime().availableProcessors();
        if (cpuCount < 1) {
            cpuCount = 1;
        }
        int threadCount = Math.min(64, cpuCount * 2);

        Thread[] threads = new Thread[threadCount];
        for (int t = 0; t < threadCount; t++) {
            threads[t] = new Thread(() -> {
                while (true) {
                    int n = nextN.getAndIncrement();
                    if (n > 239) {
                        break;
                    }
                    k1[n] = computeK1FromEstimate(n);
                }
            });
            threads[t].start();
        }

        for (Thread thread : threads) {
            try {
                thread.join();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                throw new RuntimeException("Thread interrupted", e);
            }
        }

        for (int c = 1; c <= 10; c++) {
            kD1[c] = computeK(c, 1);
        }
        for (int c = 11; c <= 160; c++) {
            kD1[c] = k1[(c + 1) / 2];
        }

        require(gValue(2, 1, kD1, k1) == 7, "Check G(2,1)");
        require(gValue(1, 2, kD1, k1) == 7, "Check G(1,2)");
        require(gValue(3, 1, kD1, k1) == 11, "Check G(3,1)");
        require(gValue(2, 2, kD1, k1) == 3, "Check G(2,2)");
        require(gValue(1, 3, kD1, k1) == 15, "Check G(1,3)");
        require(kD1[11] == computeK(11, 1), "Check k_d1[11]");
        require(kD1[57] == computeK(57, 1), "Check k_d1[57]");
        require(kD1[160] == computeK(160, 1), "Check k_d1[160]");

        BigInteger sum = BigInteger.ZERO;
        for (int c = 1; c <= 160; c++) {
            for (int d = 1; d <= 160; d++) {
                sum = sum.add(BigInteger.valueOf(gValue(c, d, kD1, k1)));
            }
        }

        return sum.toString();
    }

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