#include <bits/stdc++.h>
using namespace std;

const int N = 1e7;
using ll = long long;

bool f[N + 5];
int d[N + 5];

void sang() {
    memset(f, 1, sizeof(f));
    f[0] = f[1] = 0;
    for (int i = 2; i * i <= N; i++) {
        if (f[i]) {
            for (int j = i * i; j <= N; j += i) {
                f[j] = 0;
            }
        }
    }
    d[0] = 0;
    for (int i = 1; i <= N; i++) {
        d[i] = d[i - 1] + f[i];
    }
}

void h(int L, int R) {
    bool kt[R - L + 1];
    memset(kt, 1, sizeof(kt));

    if (L == 1)
        kt[0] = 0;

    for (int i = 2; i * i <= R; i++) {
        int s = max(i * i, (L + i - 1) / i * i);
        for (int j = s; j <= R; j += i) {
            kt[j - L] = 0;
        }
    }

    int s1 = 0;
    for (int i = 0; i <= R - L; i++) {
        if (kt[i])
            s1++;
    }
    printf("%d\n", s1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    scanf("%d", &t);

    sang();

    while (t--) {
        int L, R;
        scanf("%d %d", &L, &R);
        if (R <= N) {
            printf("%d\n", d[R] - d[L - 1]);
        } else {
            h(L, R);
        }
    }

    return 0;
}

 `-``color{#FFFFFF}{•O}``color{#CCFFFF}{W}``color{#99FFFF}{O}``color{#66FFFF}{l}``color{#33FFFF}{e}``color{#00FFFF}{g}``color{#66CCFF}{e}``color{#33CCFF}{n}``color{#00CCFF}{d}``color{#00CCCC}{l}``color{#33CCCC}{p}``color{#66CCCC}{8}``-`