#include <cstdio>
#include <algorithm>

bool tablica[1000001];
long long pierwsze[1000001], iloczyny[1000001], liczby[1000005];
long long n, a, b, wyn, k, wskaz;
long long ilo;

int main()
{
	for(int i = 2; i <= 1000000; i++)
    		tablica[i] = true;
		for(int i = 2; i <= 1000000; i++)
		{
    		if (tablica[i])
    		{
        		for(int j = 2 * i; j <= 1000000; j = j + i)
        	    	tablica[j] = false;
        	}
       	}
    for (int i = 2; i <= 1000000; i++)
   	{
    	if (tablica[i] == true)
   		{
    		pierwsze[i]++;
    		liczby[k] = i;
    		k++;
    	}
    }
    for (int i = 0; i < k; i++)
    {
    	for (int j = i; j < k; j++)
    	{
    		ilo = liczby[i] * liczby[j];
    		if (ilo <= 1000000);
    			iloczyny[ilo]++;
    	}
    }
   	scanf("%lld", &n);
    for (int i = 0; i < n; i++)
    {
    	scanf("%lld%lld", &a, &b);
    	for (int j = a; j <= b; j++)
    	{
    		if(pierwsze[j] > 0)
    			wyn++;
    		if(iloczyny[j] > 0)
    			wyn++;
    	}
    	printf("%lld\n", wyn);
    }
    getchar();
    getchar();
    return 0;
}