Two soldiers are playing a game. At the beginning first of them chooses a positive integer *n* and gives it to the second soldier. Then the second one tries to make maximum possible number of rounds. Each round consists of choosing a positive integer *x* &gt; 1, such that *n* is divisible by *x* and replacing *n* with *n* / *x*. When *n* becomes equal to 1 and there is no more possible valid moves the game is over and the score of the second soldier is equal to the number of rounds he performed.

To make the game more interesting, first soldier chooses *n* of form *a*! / *b*! for some positive integer *a* and *b* (*a* ≥ *b*). Here by *k*! we denote the factorial of *k* that is defined as a product of all positive integers not large than *k*.

What is the maximum possible score of the second soldier?
First line of input consists of single integer *t* (1 ≤ *t* ≤ 1 000 000) denoting number of games soldiers play.

Then follow *t* lines, each contains pair of integers *a* and *b* (1 ≤ *b* ≤ *a* ≤ 5 000 000) defining the value of *n* for a game.
import sys
from math import ceil,sqrt
import numpy as np
input = sys.stdin.readline
output = sys.stdout.write

N = 5000001

#doing all this in 1 list to avoid memory limit error, for clearer solution, see the commented implementation
#1.calculate the largest prime divisors for each number and storing in list P
### SEIVE OF ERATHOSTHENES METHOD
P = np.arange(0,N+1,dtype=np.int8) #[_ for _ in range(N)]

# n = input()
for i in range(2,int(ceil(sqrt(N)))+1):
    if(P[i] == i):
        for j in range(i,N,i):
            P[j] = i
# after factorising N numbers based on the numbers uptill √N integers, 
# the remaining untouched numbers are automatically prime

# 2. calculate the number of prime factors for each number and store it in list P
P[0],P[1],P[2] = 0,0,1
for i in range(3,N):
    P[i] = 1 + P[i//P[i]]
# 3. store the number of primes for i! at index i, 
#    store each at ith index as a cumulative sum of num_prime_factors until i
#
# explanation : for ith number, the number of prime factors for i! equals
# num_prime_factors[i!] = num_prime_factors[i] + num_prime_factors[i-1]
sum = 0
for i in range(N):
    sum += P[i]
    P[i] = sum


# #1.calculate the largest prime divisors for each number
# ### SEIVE OF ERATHOSTHENES METHOD
# prime_divisors = [_ for _ in range(N)]

# for i in range(2,int(ceil(sqrt(N)))+1):
#     if(prime_divisors[i] == i):
#         for j in range(i,N,i):
#             prime_divisors[j] = i
# # after factorising N numbers based on the numbers uptill √N integers, 
# # the remaining untouched numbers are automatically prime

# # 2. calculate the number of prime factors for each number
# num_prime_factors = [0 for _ in range(N)]
# num_prime_factors[0],num_prime_factors[1],num_prime_factors[2] = 0,0,1
# for i in range(3,N):
#     num_prime_factors[i] = 1 + num_prime_factors[i//prime_divisors[i]]
# # 3. store the number of primes for i! at index i, 
# #    store each at ith index as a cumulative sum of num_prime_factors until i
# #
# # explanation : for ith number, the number of prime factors for i! equals
# # num_prime_factors[i!] = num_prime_factors[i] + num_prime_factors[i-1]

# num_prime_factors_for_facts = [0 for _ in range(N)]
# sum = 0
# for i in range(N):
#     sum += num_prime_factors[i]
#     num_prime_factors_for_facts[i] = sum
# del num_prime_factors
# # cum_sum = 0
# # for i in range(2,N):
# #     cum_sum += num_prime_factors[i]
# #     print(f"{i}\t{num_prime_factors[i]}\t{cum_sum}")

t = int(input())

import time
start = time.time()
for _ in range(t):
    a, b =  map(int, input().split())
    # k = fact_div(a, b)  # fact(a) // fact(b)
    # print(k)
    output(str(P[a]-P[b]) + "\n")
    
# print(time.time()-start)
# for k in ks:
#     output(str(divide(k, 2)) + "\n")
#


"""
k:      1   2   3   4   5   6   7
rounds: 0   1   1   2   1   2   1

"""
