import java.util.ArrayList;

public class Euler656 {

    static final long kMod = 1000000000000000L;

    static class SqrtCfTail {
        int D;
        int a0;
        int m;
        int d;
        int a;

        SqrtCfTail(int value) {
            this.D = value;
            this.a0 = 0;
            while ((a0 + 1) * (a0 + 1) <= D)
                ++a0;
            this.m = 0;
            this.d = 1;
            this.a = a0;
        }

        int next() {
            m = d * a - m;
            d = (D - m * m) / d;
            a = (a0 + m) / d;
            return a;
        }
    }

    static long HMod(int beta, int g) {
        SqrtCfTail cf = new SqrtCfTail(beta);
        ArrayList<Integer> a_terms = new ArrayList<>(256);

        class Helper {
            void ensureA(int idx) {
                while (a_terms.size() < idx) {
                    a_terms.add(cf.next());
                }
            }
        }
        Helper helper = new Helper();

        ArrayList<Long> q = new ArrayList<>(512);
        q.add(0L);
        q.add(1L);
        int[] qMaxIdx = { 0 };

        class QHelper {
            void ensureQ(int idx) {
                while (qMaxIdx[0] < idx) {
                    int nextIdx = qMaxIdx[0] + 1;
                    helper.ensureA(nextIdx);
                    long aNext = a_terms.get(nextIdx - 1);
                    long qNext = (aNext * q.get(qMaxIdx[0] + 1) + q.get(qMaxIdx[0])) % kMod;
                    q.add(qNext);
                    qMaxIdx[0]++;
                }
            }
        }
        QHelper qHelper = new QHelper();

        long sum = 0;
        int produced = 0;
        int block = 0;

        while (produced < g) {
            int i = 2 * block + 1;
            qHelper.ensureQ(i - 1);
            helper.ensureA(i);

            int ai = a_terms.get(i - 1);
            long base = q.get(i - 1);
            long step = q.get(i);

            int take = Math.min(ai, g - produced);
            long term = base;
            for (int t = 0; t < take; ++t) {
                term += step;
                if (term >= kMod)
                    term -= kMod;
                sum += term;
                if (sum >= kMod)
                    sum -= kMod;
            }

            produced += take;
            ++block;
        }

        return sum;
    }

    public static String solve() {
        long total = 0;
        for (int beta = 2; beta <= 1000; ++beta) {
            int r = 0;
            while ((r + 1) * (r + 1) <= beta)
                ++r;
            if (r * r == beta)
                continue;
            total += HMod(beta, 100);
            total %= kMod;
        }
        return String.format("%015d", total);
    }

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