import java.util.Arrays;

public class Solution {
    public static int[] countSemiPrimes(int n, int[] p, int[] q) {
        boolean[] primes = new boolean[n + 1];
        Arrays.fill(primes, true);
        int[] semiPrimes = new int[n + 1];
        int[] semiPrimeCounts = new int[p.length];

        for (int i = 2; (long) i * i <= n; i++) {
            if (primes[i]) {
                for (int k = i * i; k <= n; k += i) {
                    primes[k] = false;
                }
            }
        }

        for (int k = 2; (long) k * k <= n; k++) {
            if (primes[k]) {
                for (int i = 2; i * k <= n; i++) {
                    if (primes[i]) {
                        semiPrimes[k * i] = 1;
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            semiPrimes[i] += semiPrimes[i - 1];
        }

        for (int k = 0; k < p.length; k++) {
            semiPrimeCounts[k] = semiPrimes[q[k]] - semiPrimes[p[k] - 1];
        }

        return semiPrimeCounts;
    }
}