Firstly we have to note that the second soldier should choose only prime numbers. If he choose a composite number $$$x$$$ that is equal to $$$p * q$$$, he can choose first $$$p$$$, then $$$q$$$ and get a better score. So our task is to find a number of prime factors in factorization of $$$n$$$. Now we have to note the factorization of number $$$a! / b!$$$ is this same as factorization of numbers $$$(b + 1)*(b + 2)*...*(a - 1)*a$$$. Let's count the number of prime factors in the factorization of every number from $$$2$$$ to $$$5000000$$$.

First, we use Sieve of Eratosthenes to find a prime divisor of each of these numbers. Then we can calculate a number of prime factors in factorization of a using the formula: $$$primeFactors[a] =  primeFactors[a / primeDivisor[a]]  +  1$$$ When we know all these numbers, we can use a prefix sum, and then answer for sum on interval.

import sys

input = sys.stdin.readline
dp = [0] * 5000005

def solve():
	n, m = map(int, input().split())
	print(dp[n] - dp[m])

def sieve(n):
	primes = [True] * (n + 1)
	for i in range(2, n + 1):
    	if not primes[i]:
        	continue
    	num = i * 2
    	while num <= n:
        	primes[num] = False
        	num += i

	ans = [i for i in range(2, n + 1) if primes[i]]
	return ans

def preCompute():

    
	ans = sieve(5000001)
	for a in ans:
    	dp[a] = 1

	q = int(input())

	for i in range(2, 5000001):
    	if dp[i]:
        	continue
    	d = 0
    	while ans[d] * ans[d] <= i:
        	if i % ans[d] == 0:
            	dp[i] = dp[ans[d]] + dp[i // ans[d]]
            	break
        	d += 1

	for i in range(1, 5000001):
    	dp[i] += dp[i - 1]

	for i in range(q):
    	solve()

if __name__ == "__main__":
	preCompute()