#include <iostream> 
#include <sstream> 
#include <string> 
#include <vector> 
#include <set> 
#include <map> 
#include <algorithm> 
#include <cstdio> 
#include <cstdlib> 
#include <cmath>
#include <math.h>
#include <string.h>
#include <stdlib.h>
using namespace std; 

#define REP(i, n) for(int i = 0; i<(n); i++) 
#define abs(a) ((a) >= 0 ? (a) : -(a)) 
#define inf 999999999 
typedef vector<int> VI; 
typedef vector<string> VS; 
typedef long long i64; 
typedef unsigned long long u64;
int v[10001];
int tt[100000];
int k;
int index;

int compare( const void* a, const void* b ) {
   int* arg1 = (int*) a;
   int* arg2 = (int*) b;
   return *arg1 - *arg2; 
 }
void init()
{
	k = 0;
	v[k++] = 2;
	v[k++] = 3;
	for (int i = 4; i < 100000; i++)
	{
		int j;
		int p = (int)sqrt((double)i);
		int sign = 0;
		for (j = 2; j <= p+1; j++)
			if (i%j==0) {sign = 1; break;}
		if (sign == 0) v[k++] = i;
	}
}

void go()
{
	int A, B;
	index = 0;
	for (A = 1; A < 800; A++)
		for (B = -800; B < 800; B++)
		{
			int prime[10], i;
			memset(prime, 0, sizeof(prime));
			prime[0] = 1;
			int s = 1;
			for (i = 1; i < 10; i++)
			{
				s = s*A +B;
				void *j = bsearch(&s, v, k, sizeof(int), compare);
				if (j != NULL) prime[i] = s;
				else break;
			}
			if (i<4) continue;
			else {
				i64 tmp = 1;
				tmp = tmp * prime[1] * prime[2] * prime[3];
				if (tmp > 2000000000) continue;
				else tt[index++] = tmp;
				for (int f = 4; f < i; f++)
				{
					tmp *= prime[f];
					if (tmp > 2000000000) break;
					else tt[index++] = (int)tmp;
				}	
			} 
		}	 	
	qsort(tt, index, sizeof(int), compare);
}

void compute(int x, int y)
{
	int res = 0;
	int i = 1;
	if (tt[0] >= x && tt[0] <= y) res++;
	for (i = 1; i < index; i++)
	{
		if (tt[i] == tt[i-1]) continue;
		if (tt[i] > y) break;
		if (tt[i] >=x && tt[i] <= y) res++;	
	}
	printf("%d\n", res);
	
}
int main(void)
{
	init();
	go();
	int cases;
	cin>>cases;
	for (int i = 0; i < cases; i++)
	{
		int lower, upper;
		cin>>lower>>upper;
		compute(lower, upper);		
//		printf("%d\n", compute(lower, upper));
	}
}