#include <iostream.h>
#include <time.h>
#include <stdlib.h>

static unsigned S2(unsigned x, unsigned yin);

#define cache_size 65536

int f_cache[cache_size];

static unsigned JSHpi1(unsigned xin) {

        // cache most common answers

        if (xin<cache_size) {
                if (f_cache[xin - 1] == -1)
                        f_cache[xin - 1] = xin - S2 (xin, xin) - 1;
                return f_cache[xin - 1];
        }
        return xin - S2 (xin, xin) - 1;
}

static unsigned compute_sum (unsigned i, unsigned x) {
        unsigned a1, a2, a3, sum1, sum2, j;
        a1 = JSHpi1 (i);
        a2 = JSHpi1 (i - 1);
        sum2 = a1 - a2;
        j = (i-1)*(i-1);
        if (sum2 != 0) {
                unsigned tmp2 = x / i;
                if (j < tmp2)
                        a3 = tmp2 - S2 (tmp2, j) - 1;
                else
                        a3 = JSHpi1 (tmp2);
                sum1 = a3 - a2;
                return sum1 * sum2;
        } else return 0;
}

static unsigned S2 (unsigned x, unsigned yin) {
        unsigned sum = 0, i, j, a3;

        if (4 > yin) return sum;
        int tmp2 = x / 2;
        if (2 < tmp2)
                a3 = tmp2 - S2 (tmp2, 2) - 1;
        else
                a3 = JSHpi1 (tmp2);
        sum += a3;
        if (9 <= yin) sum += compute_sum (3, x);
        if (25 <= yin) sum += compute_sum (5, x);
        for (i=6; ; i+=6) {
                j = i + 1;
                if (j*j > yin) return sum;
                sum += compute_sum (j, x);
                j = i + 5;
                if (j*j > yin) return sum;
                sum += compute_sum (j, x);
        }
}

unsigned long long pi(unsigned long long x)
{
	for(int i = 0; i < cache_size; i++) f_cache[i] = -1;
	return JSHpi1(x);
}