Babidi has summoned Majin Vegeta. He orders him to kill Supreme Kai. But Vegeta wants to get out of his control.

Babidi has laid out a trap. Vegeta is standing at the $nth$ level of mind control. In order to defeat Babidi's trap, he needs to reach $mth$ level. The levels are continuous increasing integers. At each increment of level, $nth$ to $(n+1)th$ level, for example, the energy used is - number of distinct prime factors of $n$. 

Vegeta needs your help in order to figure out how much total minimum energy he needs to defeat Babidi's trap. The total energy is the sum of energy used at each increment of a level.In the calculation of energy, $n$ and $m$ are inclusive.

------ Input: ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follow. 
The first and only line of each test case contains the two integers $n$ and $m$, separated by a single space. 

------ Output: ------
For each test case, print a single line containing one integer denoting the energy needed by Vegeta to escape Babidi's mind control and continue his battle with Kakarot.

------ Constraints  ------
$1 ≤ T ≤ 2$
$1 ≤ n ≤ m ≤ 10^{6}$

----- Sample Input 1 ------ 
2
3 7
1 1023
----- Sample Output 1 ------ 
5
2177
----- explanation 1 ------ 
Example case 1: Vegeta is standing at $n$=3. As he moves from 3 to 4, energy used is 1. From 4 to 5, energy used is 1. Similarly, as he continues to move towards m=7, the total energy used is 1+1+1+2=5.

Source: codechef | Difficulty: MEDIUM


Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [0] * m
	b = [True] * m
	count = 0
	for i in range(2, m):
		if b[i]:
			a[i] += 1
			for j in range(2 * i, m, i):
				b[j] = False
				a[j] += 1
	for i in range(n, m):
		count += a[i]
	print(count)


x = 1000000
l = [0] * (x + 1)
for i in range(2, x + 1):
	if l[i] == 0:
		j = 1
		while i * j < x + 1:
			l[i * j] = l[i * j] + 1
			j = j + 1
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	c = 0
	for i in range(n, m):
		c = c + l[i]
	print(c)


t = int(input())
for i in range(t):
	r = 0
	(n, m) = map(int, input().split())
	c = [0] * m
	a = [True] * m
	a[1] = False
	for j in range(2, m):
		if a[j]:
			c[j] += 1
			for k in range(2 * j, m, j):
				a[k] = False
				c[k] += 1
	for z in range(n, m):
		r += c[z]
	print(r)


def seive(m):
	c = [0] * m
	a = [True] * m
	a[1] = False
	for i in range(2, m):
		if a[i]:
			c[i] += 1
			for j in range(2 * i, m, i):
				a[j] = False
				c[j] += 1
	return c
for _ in range(int(input())):
	result = 0
	(n, m) = map(int, input().split())
	c = seive(m)
	for i in range(n, m):
		result += c[i]
	print(result)


prime_arr = [0] * (10 ** 6 + 1)
for i in range(2, 10 ** 6 + 1):
	if prime_arr[i] == 0:
		temp = i
		while temp <= 10 ** 6:
			prime_arr[temp] += 1
			temp += i
tests = int(input())
for i in range(tests):
	ans = 0
	(n, m) = map(int, input().split())
	for j in range(n, m):
		ans += prime_arr[j]
	print(ans)


from math import ceil, sqrt
nn = 1000000
l = [0] * (nn + 1)
for i in range(2, nn + 1):
	if l[i] == 0:
		j = 1
		while i * j <= nn:
			l[i * j] += 1
			j += 1
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	c = 0
	for i in range(n, m):
		c += l[i]
	print(c)


def sieve(n):
	global count
	count = [0] * n
	array = [True] * n
	array[1] = False
	for i in range(2, n):
		if array[i]:
			count[i] += 1
			for j in range(2 * i, n, i):
				array[j] = False
				count[j] += 1
t = int(input())
for _ in range(t):
	result = 0
	(n, m) = map(int, input().split())
	sieve(m)
	for i in range(n, m):
		result += count[i]
	print(result)


from math import ceil, sqrt
ls = [0] * (10 ** 6 + 1)
for i in range(2, 10 ** 6):
	if ls[i] == 0:
		j = 1
		while i * j <= 10 ** 6:
			ls[i * j] += 1
			j += 1
for i in range(int(input())):
	(p, q) = map(int, input().split())
	cnt = 0
	for i in range(p, q):
		cnt += ls[i]
	print(cnt)


l = [0] * (10 ** 6 + 1)
for i in range(2, 10 ** 6):
	if l[i] == 0:
		j = 1
		while i * j <= 10 ** 6:
			l[i * j] += 1
			j += 1
for i in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	for i in range(n, m):
		c += l[i]
	print(c)


from math import ceil, sqrt
l = [0] * (10 ** 6 + 1)
for i in range(2, 10 ** 6):
	if l[i] == 0:
		j = 1
		while i * j <= 10 ** 6:
			l[i * j] += 1
			j += 1
for i in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	for i in range(n, m):
		c += l[i]
	print(c)


factors = [0] * 1000001
for i in range(2, 1000001):
	if factors[i] == 0:
		factors[i] = 1
		for j in range(i + i, 1000001, i):
			factors[j] += 1
t = int(input())
while t:
	t -= 1
	ans = 0
	(n, m) = map(int, input().strip().split(' '))
	for i in range(n, m):
		ans += factors[i]
	print(ans)


divisors = [0] * 1000001
for i in range(2, 1000001):
	if divisors[i] == 0:
		divisors[i] = 1
		for j in range(i + i, 1000001, i):
			divisors[j] += 1
t = int(input())
while t:
	t -= 1
	(n, m) = list(map(int, input().split()))
	ans = 0
	for i in range(n, m):
		ans += divisors[i]
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lim = 10 ** 6
	arr = [0] * (lim + 1)
	for i in range(2, lim + 1):
		if arr[i] == 0:
			for j in range(i, lim + 1, i):
				arr[j] += 1
	print(sum(arr[n:m]))


limit = 10 ** 6 + 1
primes = [False, False] + [True] * limit
p = 2
while p * p <= limit:
	for i in range(p * 2, limit, p):
		primes[i] = False
	p += 1
prime_number = [i for (i, v) in enumerate(primes) if v]
prime_factor = [0] * limit
for prime in prime_number:
	for j in range(prime, limit, prime):
		prime_factor[j] += 1
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	print(sum(prime_factor[n:m]))


n = 1000001
fc = [0] * (n + 1)
for i in range(2, n + 1):
	if fc[i] == 0:
		for j in range(i, n + 1, i):
			fc[j] += 1
for t in range(int(input())):
	(n, m) = map(int, input().split())
	count = 0
	for i in range(n, m):
		count += fc[i]
	print(count)


import math
num = int(input())

def find_prime_numbers(n):
	res = []
	a = [0 for i in range(n + 1)]
	x = int(math.sqrt(n)) + 1
	prime = [i for i in range(n + 1)]
	for p in range(2, n):
		if prime[p]:
			a[p] += 1
			for i in range(p * 2, n + 1, p):
				a[i] += 1
				prime[i] = False
	return a

def distinct_prime_factors(n, res):
	c = 0
	x = int(math.sqrt(n))
	for i in res:
		if i > x:
			break
		if n % i == 0:
			c += 1
	return c
for i in range(num):
	s = input().split(' ')
	(n, m) = (int(s[0]), int(s[1]))
	res = 0
	x = find_prime_numbers(m)
	for j in range(n, m):
		res += x[j]
	print(res)


from math import *

def sv_of_ertsthns(n):
	prime = [1] * n
	dvsr = [0] * n
	(prime[0], prime[1]) = (0, 0)
	for i in range(2, n):
		if prime[i] == 1:
			dvsr[i] = 1
			for j in range(2 * i, n, i):
				prime[j] = 0
				dvsr[j] += 1
	return dvsr
p = sv_of_ertsthns(1000001)
for x in range(int(input())):
	(no, m) = [int(i) for i in input().split()]
	print(sum(p[no:m]))


import numpy as np

def factors():
	prime = np.ones(1000001, dtype=bool)
	p = 2
	while p * p <= 1000000:
		if prime[p] == True:
			for i in range(p * 2, 1000001, p):
				prime[i] = False
		p += 1
	return prime
prime = factors()
T = int(input())
l = []
for i in range(T):
	(n, m) = map(int, input().split())
	summ = 0
	for i in range(2, m):
		if prime[i] == True:
			summ += (m - 1) // i - (n - 1) // i
	l.append(summ)
print(*l, sep='\n')


freq = [0] * 1000001
for i in range(2, 1000001):
	if freq[i] == 0:
		for j in range(i, 1000001, i):
			freq[j] += 1
t = int(input())
for tc in range(t):
	(a, b) = map(int, input().split(' '))
	print(sum(freq[a:b]))


prime_fac = [0] * (10 ** 6 + 1)
for i in range(2, 10 ** 6 + 1):
	if prime_fac[i] == 0:
		for j in range(i, 10 ** 6 + 1, i):
			prime_fac[j] += 1
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	ans = sum(prime_fac[n:m])
	print(ans)


t = int(input())

def SieveOfEratosthenes(n):
	prime = [0] * (n + 1)
	for p in range(2, n):
		if prime[p] == 0:
			prime[p] = 1
			for i in range(p * 2, n + 1, p):
				prime[i] += 1
	return prime
p = SieveOfEratosthenes(1000000)
while t:
	(n, m) = [int(a) for a in input().strip().split()]
	print(sum(p[n:m]))
	t -= 1


T = int(input())
n = 1000001
l = [0 for i in range(n)]
for i in range(2, n):
	if l[i] == 0:
		for j in range(i, n, i):
			l[j] += 1
for test in range(T):
	sum = 0
	(N, M) = map(int, input().split())
	for item in range(N, M):
		sum += l[item]
	print(sum)


prime = [True for i in range(1000001)]
multiple = [0] * 1000001
p = 2
while p <= 1000000:
	if prime[p] == True:
		multiple[p] = 1
		for i in range(p * 2, 1000001, p):
			prime[i] = False
			multiple[i] += 1
	p += 1
t = int(input())
while t:
	(n, m) = [int(x) for x in input().split()]
	count = 0
	for i in range(n, m):
		count += multiple[i]
	print(count)
	t -= 1


from sys import stdin, stdout
from math import sqrt
from collections import defaultdict

def preProcess(n=10 ** 6 + 1):
	counter = [0 for i in range(n)]
	for i in range(2, n):
		if counter[i] == 0:
			counter[i] = 1
			for j in range(2 * i, n, i):
				counter[j] += 1
	return counter
arr = preProcess()
t = int(stdin.readline().strip())
while t > 0:
	(l, u) = [int(x) for x in stdin.readline().strip().split()]
	print(sum(arr[l:u]))
	t -= 1


p_count = 10 ** 6 + 1
primes = [True] * p_count
primes[0] = primes[1] = False
p = 2
while p * p <= p_count:
	for i in range(p * 2, p_count, p):
		primes[i] = False
	p += 1
prime_number = [i for (i, value) in enumerate(primes) if value]
prime_factors = [0] * (10 ** 6 + 1)
for prime in prime_number:
	for i in range(prime, 10 ** 6 + 1, prime):
		prime_factors[i] += 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(sum(prime_factors[n:m]))


def prime_numbers():
	nums = [True for i in range(1000001)]
	count = [0 for i in range(1000001)]
	for i in range(2, 1000001):
		if nums[i]:
			count[i] = 1
			for j in range(2 * i, 1000001, i):
				nums[j] = False
				count[j] += 1
	return count
t = int(input())
count = prime_numbers()
while t > 0:
	st = input().split()
	n = int(st[0])
	m = int(st[1])
	ans = 0
	for i in range(n, m):
		ans += count[i]
	print(ans)
	t -= 1


maxn = 1000010
spf = [0] * maxn

def sieve():
	for i in range(1, maxn):
		if i % 2 == 0:
			spf[i] = 2
		else:
			spf[i] = i
	i = 3
	while i * i < maxn:
		if spf[i] == i:
			for j in range(i * i, maxn, i):
				if spf[j] == j:
					spf[j] = i
		i += 1
sieve()

def getFactors(n):
	l = []
	while n != 1:
		l.append(spf[n])
		n = n // spf[n]
	return l
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	for i in range(n, m):
		ans += len(set(getFactors(i)))
	print(ans)


p = 1000001 * [0]
for i in range(2, 1000001):
	if p[i] == 0:
		for j in range(i, 1000001, i):
			p[j] += 1
for _ in range(int(input())):
	(n, m) = [int(j) for j in input().split()]
	tot = 0
	for i in range(n, m):
		tot += p[i]
	print(tot)


p = [0] * 1000002
for i in range(2, 1000001):
	if p[i] == 0:
		for j in range(i, 1000001, i):
			p[j] += 1
t = int(input())
for test in range(t):
	(n, m) = map(int, input().split())
	print(sum(p[n:m]))


n = 1000001
fc = [0] * (n + 1)
for i in range(2, n + 1):
	if fc[i] == 0:
		for j in range(i, n + 1, i):
			fc[j] = fc[j] + 1
for hhh in range(0, int(input())):
	(a, b) = list(map(int, input().split()))
	c = 0
	for i in range(a, b):
		c = c + fc[i]
	print(c)


def get_value(n, m):
	for i in range(6):
		if ar[i] == 0:
			flag = 0

def get_name(a, b):
	for i in range(6):
		if x[i] == 0:
			cnt = 0

def factorization(n):
	for i in range(2, 1000005):
		if n[i] == 0:
			n[i] = 1
			for j in range(i + i, 1000001, i):
				n[j] += 1

def show(a, b):
	a = input()
	b = input()
	print(a + b)

def print_answer(count):
	print(count)
for i in range(int(input())):
	count = 0
	n = [0] * 1000005
	factorization(n)
	(x, y) = map(int, input().split(' '))
	while x < y:
		count = count + n[x]
		x = x + 1
	print_answer(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	fac = [0] * m
	for i in range(2, m):
		if fac[i] == 0:
			for j in range(i, m, i):
				fac[j] += 1
	print(sum(fac[n:m]))


def primefactors():
	arr = []
	n = 10 ** 6
	arr.append(1)
	for i in range(n):
		if i % 2 == 1:
			arr.append(2)
		else:
			arr.append(i + 1)
	for i in range(3, n):
		if i * i < n:
			for j in range(i * i, n, i):
				if arr[j] == j:
					arr[j] = i
		else:
			break
	return arr
y = int(input())
abc = primefactors()
for i in range(y):
	x = [int(i) for i in input().split()]
	n = x[0]
	m = x[1]
	sum1 = 0
	for j in range(n, m):
		arr = []
		a = j
		while a != 1:
			arr.append(abc[a])
			a = a // abc[a]
		sum1 += len(list(set(arr)))
	print(sum1)


test = int(input())
for i in range(test):
	(b, c) = input().split()
	b = int(b)
	c = int(c)
	max = c
	nb_factors = [0] * max
	for i in range(2, max):
		if nb_factors[i] == 0:
			for j in range(i, max, i):
				nb_factors[j] += 1
	add = 0
	for (i, f) in enumerate(nb_factors):
		if i >= b:
			add = add + f
	print(add)


def prime_factors(l):
	for i in range(2, 1000001):
		if l[i] == 0:
			l[i] = 1
			for j in range(i + i, 1000001, i):
				l[j] += 1
for i in range(int(input())):
	l = [0] * 1000001
	prime_factors(l)
	(a, b) = map(int, input().split(' '))
	(sum, n) = (0, 0)
	while a < b:
		sum += l[a]
		a += 1
	print(sum)


def sieve():
	prime = [True for i in range(1000001)]
	p = 2
	while p * p <= 1000001:
		if prime[p] == True:
			for i in range(p * 2, 1000001, p):
				prime[i] = False
		p += 1
	return prime
primeArr = sieve()
primeArr[1] = False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ans = 0
	for i in range(2, m):
		if primeArr[i] == True:
			ans += (m - 1) // i - (n - 1) // i
	print(ans)


def sieve():
	p = 10 ** 6 + 1
	fact = [0] * (10 ** 6 + 2)
	i = 2
	while i <= p:
		if fact[i] == 0:
			for j in range(i, p + 1, i):
				fact[j] += 1
		i += 1
	return fact
fact = sieve()
t = int(input())
while t:
	(n, m) = map(int, input().split())
	print(sum(fact[n:m]))
	t = t - 1


pf = [i for i in range(1, 10 ** 6 + 1)]
had = [0 for i in range(10 ** 6)]
pf[0] = 0
for i in range(1, len(pf)):
	if not had[i]:
		for j in range(i * 2 + 1, len(pf), i + 1):
			if not had[j]:
				pf[j] = 1
				had[j] = 1
			else:
				pf[j] += 1
		pf[i] = 1

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = [int(x) for x in input().split()]
		if m == n:
			ans = 0
		else:
			ans = sum(pf[n - 1:m - 1] + [0])
		print(ans)

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
main()


Max = 1000005

def fillPrimeCount(A):
	index = 2
	while index < Max:
		if A[index] != 0:
			while index < Max and A[index] != 0:
				index += 1
		else:
			inc = index
			count = 1
			while inc * count < Max:
				A[inc * count] += 1
				count += 1
primeCount = [0 for i in range(Max)]
fillPrimeCount(primeCount)
test = int(input())
for test in range(test):
	(n, m) = [int(x) for x in input().split()]
	print(sum(primeCount[n:m]))


maxa = 1000001
arrr = []
for i in range(maxa):
	arrr.append(0)
for i in range(1, maxa):
	arrr[i] = i
for i in range(4, maxa, 2):
	arrr[i] = 2
i = 3
while i * i < maxa:
	if arrr[i] == i:
		j = i * i
		while j < maxa:
			if arrr[j] == j:
				arrr[j] = i
			j += i
	i += 1

def give_count_primes(arrr, x):
	count = []
	while x != 1:
		count.append(arrr[x])
		x = x // arrr[x]
	return len(set(count))
t = int(input())
for w in range(t):
	yoar = list(map(int, input().split()))
	n = yoar[0]
	m = yoar[1]
	anscount = 0
	for i in range(n, m):
		anscount += give_count_primes(arrr, i)
	print(anscount)


a = [0] * 1000001
a[0] = 0
a[1] = 0
for i in range(2, 1000001):
	if a[i] == 0:
		a[i] += 1
		for j in range(i * 2, 1000001, i):
			a[j] += 1
for test in range(int(input())):
	(n, m) = map(int, input().strip().split())
	ans = 0
	for k in range(n, m):
		ans += a[k]
	print(ans)


def fun(n):
	mi = [0] * (n + 1)
	for i in range(2, int(n ** (1 / 2))):
		if mi[i] == 0:
			for j in range(i * i, n + 1, i):
				if mi[j] == 0:
					mi[j] = i
	for i in range(2, n + 1):
		if mi[i] == 0:
			mi[i] = i
	return mi

def fact(n, arr):
	a = []
	while n != 1:
		a.append(arr[n])
		n = int(n / arr[n])
	return len(set(a))
arr = fun(10 ** 6 + 1)
t = int(input())
for isdx in range(t):
	(n, m) = [int(x) for x in input().split()]
	c = 0
	for i in range(n, m):
		c += fact(i, arr)
	print(c)


l = [0 for i in range(1000002)]
i = 2
while i < 1000002:
	if l[i] == 0:
		k = i
		c = 1
		while k * c < 1000002:
			l[k * c] += 1
			c += 1
	else:
		while i < 1000002 and l[i] != 0:
			i += 1
t = int(input())
for test in range(t):
	(n, m) = map(int, input().split())
	print(sum(l[n:m]))


import sys
fa = [0] * (10 ** 6 + 1)
for i in range(2, 10 ** 6 + 1):
	if fa[i] == 0:
		for j in range(i, 10 ** 6 + 1, i):
			fa[j] += 1
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	a = 0
	for i in range(n, m):
		a += fa[i]
	sys.stdout.write(str(a))
	print()


MAX = int(1000000.0) + 1
p = [True] * MAX
c = [0] * MAX
for i in range(2, MAX):
	if p[i]:
		for j in range(i, MAX, i):
			p[j] = False
			c[j] += 1
for i in range(1, MAX):
	c[i] += c[i - 1]
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	print(c[b - 1] - c[a - 1])


factor_count = [0] * (10 ** 6 + 1)
for i in range(2, 10 ** 6 + 1):
	if factor_count[i] == 0:
		for j in range(i, 10 ** 6 + 1, i):
			factor_count[j] += 1
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	for i in range(n, m):
		ans += factor_count[i]
	print(ans)