/**
 * Sample solution to Exploding CPUs 
 * Author: Mikael Goldmann
 * Based on simple observation that p1 and p2 must be fairly small
 * Sloppy bound on pn is 2*10^6  (pn < (2*10^9)^(2/3))
 */

import java.util.*;
import java.io.*;

class Cpu
{
    static final int MAXP = 2000000;
    
    static BufferedReader stdin = 
	new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer tokens = new StreamTokenizer(stdin);
    
    
    static PrintWriter stdout = 
	new PrintWriter(
			new BufferedWriter(new OutputStreamWriter(System.out)));
    static boolean[] isprime;
    
    
    static int getInt() throws IOException
    {
	tokens.nextToken();
	return (int)Math.round(tokens.nval);
    }
    
    public static void main(String[] as)  throws IOException
    {
	int n = getInt();
	init();
	for (int i = 0; i < n; ++i)
	    solve();
	stdout.close();
    }
    
    
    static void solve() throws IOException
    {
	int lo = getInt();
	int hi = getInt();
	int ans = exploding(hi) - exploding(lo-1);
	stdout.println(ans);
    }
    
    
    static void init() 
    {
	isprime = new boolean[MAXP+1];
	Arrays.fill(isprime, true);
	isprime[0] = isprime[1] = false;
	for (int i = 2; i <= MAXP; ++i) {
	    if (isprime[i]) {
		for (int j = 2*i; j <= MAXP; j += i)
		    isprime[j] = false;
	    }
	}
    }
    
    static int exploding(long m) 
    {
	int A, B, p1, p2, p3;
	int nexpl = 0;	
	for (p1 = 2; p1*p1*p1 <= m; ++p1)
	    if (isprime[p1]) {
		// System.err.println("p1 = " + p1);
		for (p2 = p1+1; p1*p2*p2 <= m; ++p2) {
		    if (isprime[p2]) {
			// System.err.println("  p2 = " + p2);
			A = (p2 -p1) / (p1-1);
			if ( A*(p1-1) != p2-p1 ) continue;
			B = p1 - A;
			p3 = A*p2 + B;
			long prod = p1;
			prod *= p2;		    
			if (isprime[p2] && p2 != p1) {
			    while (true) {
				// System.err.println("    p3 = " + p3);
				prod *= p3;
				if (prod > m || !isprime[p3]) break;  
				else {
				    // System.err.println(">" + prod);
				    
				    ++nexpl;
				    p3 = A*p3+B;
				}
			    }
			}
		    }
		}
	    }
	
	return nexpl;
    }
}