#include <iostream>
using namespace std;

bool tablica[1000001] = {};
int tablica2[1000001] = {};

void sito(bool* tab, int n)
{
    tab[1] = 1;
    tab[0] = 1;

    for (int i = 2; i * i <= n; i++)
    {
        if (!tab[i])
        {
            for (int j = i * i; j <= n; j += i)
                tab[j] = 1;
        }
    }
}
void zamiana(bool* tab, int* tablica, int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!tab[i])
        {
            tablica[i] = tablica[i - 1] + 1;
        }
        else
        {
            tablica[i] = tablica[i - 1];
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    sito(tablica, 1000000);
    zamiana(tablica, tablica2, 1000000);
    int test;
    cin >> test;
    for (int t = 0; t < test; t++)
    {
        int suma, dolny, gorny;

        cin >> dolny >> gorny;
        suma = tablica2[gorny] - tablica2[dolny - 1];
        cout << suma << '\n';
    }
    return 0;
}