public class Euler769 {
    static long isqrt(long x) {
        if (x < 0)
            throw new IllegalArgumentException();
        if (x == 0)
            return 0;
        long r = (long) Math.sqrt((double) x);
        long y = r;
        while ((y + 1) * (y + 1) <= x)
            ++y;
        while (y * y > x)
            --y;
        return y;
    }

    static int[] buildSpf(int limit) {
        int[] spf = new int[limit + 1];
        if (limit >= 1)
            spf[1] = 1;
        for (int i = 2; i <= limit; ++i) {
            if (spf[i] == 0) {
                spf[i] = i;
                if ((long) i * i <= limit) {
                    for (int j = i * i; j <= limit; j += i) {
                        if (spf[j] == 0)
                            spf[j] = i;
                    }
                }
            }
        }
        return spf;
    }

    static class Counter {
        int[] spf;
        double alpha;
        double beta;
        int[] inv13 = new int[13];

        Counter(int[] spfRef) {
            spf = spfRef;
            alpha = 2.0 - Math.sqrt(3.0);
            beta = 2.0 + Math.sqrt(3.0);

            for (int i = 1; i < 13; ++i) {
                for (int j = 1; j < 13; ++j) {
                    if ((i * j) % 13 == 1) {
                        inv13[i] = j;
                        break;
                    }
                }
            }
        }

        void buildSquarefreeDivs(int q, int[] divs, int[] mus, int[] countOut) {
            divs[0] = 1;
            mus[0] = 1;
            int count = 1;
            int x = q;
            while (x > 1) {
                int p = spf[x];
                while (x % p == 0)
                    x /= p;
                int current = count;
                for (int i = 0; i < current; ++i) {
                    divs[count] = divs[i] * p;
                    mus[count] = -mus[i];
                    count++;
                }
            }
            countOut[0] = count;
        }

        long coprimeCount(int[] divs, int[] mus, int count, long kMax) {
            if (kMax <= 0)
                return 0;
            long total = 0;
            for (int i = 0; i < count; ++i) {
                total += mus[i] * (kMax / divs[i]);
            }
            return total;
        }

        long coprimeCountResidue(int[] divs, int[] mus, int count, long kMax, int residue) {
            if (kMax <= 0)
                return 0;
            long total = 0;
            for (int i = 0; i < count; ++i) {
                int d = divs[i];
                int dMod = d % 13;
                int inv = inv13[dMod];
                int t0 = (residue * inv) % 13;
                if (t0 == 0)
                    continue;
                long first = (long) d * t0;
                if (first > kMax)
                    continue;
                total += mus[i] * (1 + (kMax - first) / (13L * d));
            }
            return total;
        }

        long countWithResidue(int[] divs, int[] mus, int count, long kMax, int qMod13, int residue) {
            if (kMax <= 0)
                return 0;
            long base = coprimeCount(divs, mus, count, kMax);
            if (qMod13 != 0) {
                base -= coprimeCountResidue(divs, mus, count, kMax, residue);
            }
            return base;
        }

        long countExclude13(int[] divs, int[] mus, int count, long kMax, int qMod13) {
            if (kMax <= 0)
                return 0;
            long base = coprimeCount(divs, mus, count, kMax);
            if (qMod13 != 0) {
                base -= coprimeCount(divs, mus, count, kMax / 13);
            }
            return base;
        }

        long compute(long N) {
            long qLimit = isqrt(N);
            if (qLimit == 0)
                return 0;

            long total = 0;
            int[] divs = new int[256];
            int[] mus = new int[256];
            int[] countOut = new int[1];

            for (long q = 1; q <= qLimit; ++q) {
                buildSquarefreeDivs((int) q, divs, mus, countOut);
                int cnt = countOut[0];

                long q2 = q * q;
                int qMod13 = (int) (q % 13);
                int residue = qMod13 == 0 ? 0 : (13 - (2 * qMod13) % 13) % 13;

                // Region A
                long kMax = (long) Math.floor(alpha * q);
                if (kMax > 0) {
                    while (kMax > 0) {
                        long xVal = q2 - 4 * q * kMax + kMax * kMax;
                        if (xVal > 0)
                            break;
                        kMax--;
                    }
                    if (kMax > 0) {
                        long base = countWithResidue(divs, mus, cnt, kMax, qMod13, residue);
                        long disc = 13 * q2 - 12 * N;
                        if (disc > 0) {
                            long s = isqrt(disc);
                            long L = (q - s + 5) / 6;
                            long R = (q + s) / 6;

                            while (L <= kMax && (q2 + q * L - 3 * L * L) <= N)
                                L++;
                            while (R >= 1 && (q2 + q * R - 3 * R * R) <= N)
                                R--;

                            if (L <= R && L <= kMax && R >= 1) {
                                long L2 = Math.max(1, L);
                                long R2 = Math.min(kMax, R);
                                if (L2 <= R2) {
                                    long forbidden = countWithResidue(divs, mus, cnt, R2, qMod13, residue) -
                                            countWithResidue(divs, mus, cnt, L2 - 1, qMod13, residue);
                                    base -= forbidden;
                                }
                            }
                        }
                        total += base;
                    }
                }

                // discPlus
                // Note: 13 * q^2 + 12 * N can be up to 13*10^14 + 12*10^14 = 2.5 * 10^15 (fits
                // in long)
                long discPlus = 13 * q2 + 12 * N;
                long sPlus = isqrt(discPlus);

                // Region C
                long kMaxC = (sPlus - 13 * q) / 6;
                if (kMaxC > 0) {
                    while (kMaxC > 0 && (13 * q2 + 13 * q * kMaxC + 3 * kMaxC * kMaxC) > N)
                        kMaxC--;
                    while ((13 * q2 + 13 * q * (kMaxC + 1) + 3 * (kMaxC + 1) * (kMaxC + 1)) <= N)
                        kMaxC++;
                    if (kMaxC > 0) {
                        total += countExclude13(divs, mus, cnt, kMaxC, qMod13);
                    }
                }

                // Region D
                long kMinD = (long) Math.floor(beta * q) + 1;
                if (kMinD < 1)
                    kMinD = 1;
                while (true) {
                    long xVal = q2 - 4 * q * kMinD + kMinD * kMinD;
                    if (xVal > 0)
                        break;
                    kMinD++;
                }

                long kMaxD = (sPlus + q) / 6;
                while (kMaxD > 0 && (3 * kMaxD * kMaxD - q * kMaxD - q2) > N)
                    kMaxD--;
                while ((3 * (kMaxD + 1) * (kMaxD + 1) - q * (kMaxD + 1) - q2) <= N)
                    kMaxD++;

                if (kMinD <= kMaxD) {
                    total += countWithResidue(divs, mus, cnt, kMaxD, qMod13, residue) -
                            countWithResidue(divs, mus, cnt, kMinD - 1, qMod13, residue);
                }
            }

            if (N >= 3) {
                total += 1;
            }

            return total;
        }
    }

    public static String solve() {
        long n = 100000000000000L;
        int qLimit = (int) isqrt(n);
        int[] spf = buildSpf(qLimit);
        Counter c = new Counter(spf);
        long ans = c.compute(n);
        return Long.toString(ans);
    }

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