Chef has a new customer and he wants to prepare his order as soon as possible. While preparing, he sees that the mint sauce is finished. He has to run upstairs to get it from other kitchen. Chef is currently on the X^{th} stair. He has to climb all the way up to the Y^{th} stair in minimum number of steps. In one step, Chef can do one of the following things: 

Climb a single stair. ( i.e go from the X^{th} stair to the (X+1)^{th} stair. ) 
Climb two stairs only if the final stair falls at a prime number position. ( i.e. go from the X^{th} stair to the (X+2)^{th} stair, only if (X + 2) is a prime number) 

Help Chef reach the Y^{th} stair from the X^{th} stair in minimum number of steps. 

\textbf{See Explanation for more clarity.}

Note: The input files are large. The use of Fast I/O is recommended.

------ Input Format ------ 

- The first line contains an integer T denoting the number of test cases. The T test cases then follow.
- The first line of each test case contains X and Y denoting the starting stair and ending stair respectively.

------ Output Format ------ 

- Output a single integer representing minimum number of steps chef can take to reach from X^{th} to Y^{th} stair.

------ Constraints ------ 

$1 ≤ T ≤ 10^{6}$
$1 ≤ X < Y ≤ 10^{7}$

----- Sample Input 1 ------ 
4
2 10
5 12
34 43
57 63
----- Sample Output 1 ------ 
6
5
6
4
----- explanation 1 ------ 
Test case $1$: Chef starts from $2^{nd}$, goes to $3^{rd}$ stair, then to $5^{th}$ stair as $5$ or $(3+2)$ is prime number. Now, from $5^{th}$ stair, Chef goes to $7^{th}$ stair as $7$ or $(5+2)$ is a prime number, then Chef goes to $8^{th}$ stair, then to $9^{th}$ stair and finally to $10^{th}$ stair. This approach takes a total of $6$ steps which is the minimum possible number of steps Chef can take to reach the $10^{th}$ stair starting from the $2^{nd}$ stair. 

Test case $3$: Starting from the $34^{th}$ stair, Chef moves through the stairs as following. $34$ → $35$ → $37$ → $38$ → $39$ → $41$ → $43$.

Source: codechef | Difficulty: HARD
Tags: Number theory

Dynamic programming

Mathematics


Solutions:
maxN = 10000009
prime = [1 for i in range(maxN + 1)]
i = 2
while i * i <= maxN:
	if prime[i]:
		for j in range(i ** 2, maxN + 1, i):
			prime[j] = False
	i += 1
(prime[0], prime[1]) = [0] * 2
for i in range(1, maxN + 1):
	prime[i] += prime[i - 1]
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	cnt = 0
	print(y - x - (prime[y] - prime[x + 1]))


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
pr = lambda x: x

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def SieveOfEratosthenes(n):
	Z = []
	prime = [1 for i in range(n + 1)]
	p = 2
	prime[0] = prime[1] = 0
	while p * p <= n:
		if prime[p] == 1:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
		p += 1
	return prime
pri = list(accumulate(SieveOfEratosthenes(10000010)))
for i in range(int(input())):
	(x, y) = map(int, input().split())
	ans = y - x
	if x == y:
		print(0)
	elif y == x + 1:
		print(1)
	else:
		primes = pri[y] - pri[x + 1]
		ans -= primes
		print(ans)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
A = SieveOfEratosthenes(10000010)
B = [0, 0]
for i in range(2, 10000009):
	if A[i]:
		B.append(B[-1] + 1)
	else:
		B.append(B[-1])
for t in range(int(input())):
	(X, Y) = map(int, input().split())
	if X == Y:
		print(0)
		continue
	elif X == Y - 1:
		print(1)
		continue
	temp = B[Y] - B[X + 1]
	print(Y - X - temp)


from sys import stdin
data = stdin.read().split('\n')
n = 10000000
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p ** 2, n + 1, p):
			prime[i] = False
	p += 1
prime[0] = False
prime[1] = False
lookup = {0: 0, 1: 0}
k = 0
for p in range(n + 1):
	if prime[p]:
		k += 1
		lookup[p] = k
	else:
		lookup[p] = k
for i in range(int(data[0])):
	(X, Y) = map(int, data[i + 1].split(' '))
	total = Y - X
	ans = lookup[Y] - lookup[X]
	ans += total - ans * 2
	if prime[X + 1]:
		ans += 1
	print(ans)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
maxi = 10 ** 7 + 1
stat = [0 for i in range(maxi)]
stat[0] = 1
stat[1] = 1
for i in range(2, int(sqrt(maxi) + 1)):
	if stat[i] == 0:
		for j in range(i * i, maxi, i):
			stat[j] = 1
pr_c = [0 for i in range(maxi)]
a = 0
for i in range(maxi):
	if stat[i] == 0:
		a += 1
	pr_c[i] = a
for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	ans = y - x - (pr_c[y] - pr_c[x + 1])
	print(ans)


from itertools import accumulate

def generate_primes(n):
	primes = [True for x in range(n + 1)]
	num = 2
	while num * num <= n:
		if primes[num]:
			for i in range(num ** 2, n + 1, num):
				primes[i] = False
		num += 1
	primes[0] = False
	primes[1] = False
	return primes
t = int(input().strip())
primes = list(accumulate(generate_primes(10 ** 7 + 1)))
while t > 0:
	t -= 1
	(x, y) = map(int, input().strip().split())
	if x == y:
		print(0)
	elif x + 1 == y:
		print(1)
	else:
		steps = y - x - (primes[y] - primes[x + 1])
		print(steps)


def sieve_of_eratosthenes(n):
	lis = [True for x in range(0, n + 1)]
	(lis[0], lis[1]) = (False, False)
	for i in range(2, int(n ** 0.5) + 1):
		if lis[i] == True:
			for j in range(i * 2, n + 1, i):
				lis[j] = False
	lis1 = [0]
	for i in range(1, n + 1):
		if lis[i] == True:
			lis1.append(lis1[i - 1] + 1)
		else:
			lis1.append(lis1[i - 1])
	return lis1
l = sieve_of_eratosthenes(10 ** 7)
for i in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	print(y - x - (l[y] - l[x + 1]))


from itertools import accumulate

def makeIsPr(p_limit):
	track = [False, True] * (p_limit // 2 + 1)
	if p_limit % 2 == 0:
		track.pop()
	track[0:3] = [False, False, True]
	pc = 3
	while pc * pc <= p_limit:
		if track[pc]:
			for a in range(pc * pc, p_limit + 1, 2 * pc):
				track[a] = False
		pc += 2
	return track
pCount = list(accumulate(makeIsPr(10 ** 7)))
for _ in range(int(input())):
	(S, E) = map(int, input().split())
	print(E - S - (pCount[E] - pCount[S + 1]))


n = 10000007
prime = [True for i in range(n + 1)]

def SieveOfEratosthenes():
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
SieveOfEratosthenes()
pre = [0] * n
for i in range(1, n):
	if prime[i] == True:
		pre[i] = pre[i - 1] + 1
	else:
		pre[i] = pre[i - 1]
for i in range(int(input())):
	(x, y) = map(int, input().split())
	print(y - x - (pre[y] - pre[x + 1]))


def main():
	primes = [1] * 10000001
	for i in range(2, 10002):
		if primes[i] == 1:
			for j in range(i + i, 10000001, i):
				primes[j] = 0
	primes[0] = 0
	primes[1] = 0
	for i in range(1, len(primes)):
		primes[i] = primes[i] + primes[i - 1]
	for _ in range(int(input())):
		(X, Y) = map(int, input().split())
		c = Y - X
		n = primes[Y] - primes[X + 1]
		print(c - n)
main()


from itertools import groupby, accumulate

def solve():

	def SieveOfEratosthenes(n):
		Z = []
		prime = [1 for i in range(n + 1)]
		p = 2
		prime[0] = prime[1] = 0
		while p * p <= n:
			if prime[p] == 1:
				for i in range(p * p, n + 1, p):
					prime[i] = 0
			p += 1
		return prime
	pri = list(accumulate(SieveOfEratosthenes(10000010)))
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		ans = y - x
		if x == y:
			print(0)
		elif y == x + 1:
			print(1)
		else:
			primes = pri[y] - pri[x + 1]
			ans -= primes
			print(ans)
solve()


from sys import stdin
from itertools import accumulate

def makeIsPr(p_limit):
	track = [False, True] * (p_limit // 2 + 1)
	if p_limit % 2 == 0:
		track.pop()
	track[0:3] = [False, False, True]
	pc = 3
	while pc * pc <= p_limit:
		if track[pc]:
			for a in range(pc * pc, p_limit + 1, 2 * pc):
				track[a] = False
		pc += 2
	return track
lim = 10000000
isPrime = makeIsPr(lim)
pCount = list(accumulate(isPrime))
inp = stdin.readline
T = int(inp())
ans = []
for _ in range(T):
	(S, E) = map(int, inp().split())
	ans.append(E - S - (pCount[E] - pCount[S + 1]))
print(*ans, sep='\n')


maxn = 10000000.0
x = int(maxn + 2)
isPrime = [True] * x
totalPrime = [0] * x
n = int(maxn)
isPrime[0] = False
isPrime[1] = False
i = 2
for i in range(2, n + 1):
	totalPrime[i] = totalPrime[i - 1]
	if isPrime[i] == True:
		totalPrime[i] += 1
		for j in range(i * i, n + 1, i):
			isPrime[j] = False
T = int(input())
for i in range(T):
	(X, Y) = map(int, input().split())
	count = Y - X - (totalPrime[Y] - totalPrime[X + 1])
	print(count)


import sys
import bisect
input = sys.stdin.readline

def SieveOfEratosthenes(n):
	arr = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			arr.append(p)
	return arr

def solve():
	(a, b) = map(int, input().split())
	ans = b - a
	(l, r) = (bisect.bisect_left(primes, a + 2), bisect.bisect_left(primes, b))
	ans -= r - l
	if len(primes) != r and primes[r] == b:
		ans -= 1
	print(ans)
t = int(input())
primes = SieveOfEratosthenes(10 ** 7)
for _ in range(t):
	solve()


import sys
import math
N = 10000002
is_prime = [1] * N
is_prime[0] = 0
is_prime[1] = 0

def sieve():
	i = 2
	while i * i <= N:
		if is_prime[i] == 0:
			i += 1
			continue
		j = 2 * i
		while j < N:
			is_prime[j] = 0
			j += i
		i += 1
sieve()
total_primes = [0] * N
for i in range(1, N):
	total_primes[i] = is_prime[i] + total_primes[i - 1]
for case in range(int(input())):
	[X, Y] = map(int, sys.stdin.readline().split())
	print(Y - X - (total_primes[Y] - total_primes[X + 1]))


import sys
from math import sqrt

def read(typ=str):
	return list(map(typ, sys.stdin.readline().split()))
y = int(10000000.0)
prime = [1] * (y + 1)
for i in range(2, int(sqrt(y)) + 1):
	if prime[i] == 1:
		for j in range(i * i, y + 1, i):
			prime[j] = 0
pcount = 0
pre = [0] * (y + 1)
for i in range(y + 1):
	if prime[i] == 1:
		pcount += 1
	pre[i] = pcount
t = read(int)[0]
for _ in range(t):
	(x, y) = read(int)
	count = pre[y] - pre[x]
	if prime[x + 1] == 1:
		count -= 1
	print(y - x - count)


a = int(input())
MAX = 10000000
prefix = [0] * (MAX + 1)

def buildPrefix():
	prime = [1] * (MAX + 1)
	p = 2
	while p * p <= MAX:
		if prime[p] == 1:
			i = p * 2
			while i <= MAX:
				prime[i] = 0
				i += p
		p += 1
	for p in range(2, MAX + 1):
		prefix[p] = prefix[p - 1]
		if prime[p] == 1:
			prefix[p] += 1

def query(L, R):
	return prefix[R] - prefix[L - 1]
buildPrefix()
for i in range(a):
	b = list(map(int, input().split()))
	rnum = b[-1] - b[0] + 1
	print(rnum - query(b[0] + 2, b[-1]) - 1)


def is_prime(n):
	if n % 2 == 0 and n != 2:
		return False
	for j in range(3, int(n ** 0.5) + 1, 2):
		if n % j == 0:
			return False
	return True
n = 10 ** 7
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p * p, n + 1, p):
			prime[i] = False
	p += 1
arr = [0] * (n + 1)
cnt = 0
for p in range(2, n + 1):
	if prime[p]:
		cnt += 1
	arr[p] = cnt
for i in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	ans = arr[b] - arr[a + 1]
	print(b - a - ans)


import sys
ins = lambda : sys.stdin.readline().strip()
inarr = lambda s: list(map(s, sys.stdin.readline().strip().split()))
outs = lambda n: sys.stdout.write(str(n) + '\n')
outarr = lambda li: sys.stdout.write(' '.join(map(str, li)) + '\n')

def sieve(n):
	prime = [1 for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == 1:
			for j in range(p ** 2, n + 1, p):
				prime[j] = 0
		p += 1
	prime[0] = 0
	prime[1] = 0
	for j in range(1, n + 1):
		prime[j] += prime[j - 1]
	return prime
prime = sieve(10000009)
for _ in range(int(input())):
	(x, y) = inarr(int)
	if x + 2 <= y:
		total_prime = prime[y] - prime[x + 1]
		outs(y - x - total_prime)
	else:
		outs(y - x)


n = 10 ** 7
primes = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if primes[p] == True:
		for i in range(p * p, n + 1, p):
			primes[i] = False
	p = p + 1
pre = [0] * (n + 1)
for i in range(2, n + 1):
	if primes[i]:
		pre[i] = pre[i - 1] + 1
	else:
		pre[i] = pre[i - 1]
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if x == 1 and y == 3:
		print(2)
		continue
	if primes[x + 1]:
		ans = y - x - (pre[y] - pre[x]) + 1
	else:
		ans = y - x - (pre[y] - pre[x])
	print(ans)


l1 = [1] * 10000001
l1[0] = 0
l1[1] = 0
for i in range(2, 3163):
	if l1[i] == 1:
		temp = i * i
		while temp < 10000001:
			l1[temp] = 0
			temp = temp + i
l2 = [0] * 10000001
for i in range(2, len(l1)):
	if l1[i] == 1:
		l2[i] = l2[i - 1] + 1
	else:
		l2[i] = l2[i - 1]
for t in range(int(input())):
	(x, y) = map(int, input().split())
	res = y - x - (l2[y] - l2[x + 1])
	print(res)


from sys import stdin, stdout
from math import ceil, sqrt
from bisect import bisect_left

def sieve(MAXN):
	is_prime[0] = is_prime[1] = 0
	for i in range(4, MAXN, 2):
		is_prime[i] = 0
	for i in range(3, ceil(sqrt(MAXN)), 2):
		if is_prime[i]:
			for j in range(i * i, MAXN + 1, i * 2):
				is_prime[j] = 0
	primes.append(2)
	for i in range(3, MAXN, 2):
		if is_prime[i]:
			primes.append(i)
N = int(10000000.0 + 10)
primes = []
is_prime = [1 for _ in range(N)]
sieve(N)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	(t1, t2) = (bisect_left(primes, y + 1), bisect_left(primes, x + 1))
	ans = y - x + t2 - t1
	if x + 1 == primes[t2]:
		ans += 1
	print(ans)


n = 10 ** 7 + 2
s = [1] * n
s[0] = 0
s[1] = 0
for i in range(2, int(n ** 0.5) + 1):
	if s[i]:
		for j in range(2 * i, n, i):
			s[j] = 0
freq = [0] * n
for i in range(2, n):
	freq[i] = freq[i - 1] + s[i]
for i in range(int(input())):
	(x, y) = map(int, input().split())
	ans = y - x - (freq[y] - freq[x + 1])
	print(ans)


import math as m
from itertools import accumulate

def Sieve(n):
	isPrime = [True] * (n + 1)
	isPrime[0] = isPrime[1] = False
	for i in range(2, int(m.sqrt(n))):
		if isPrime[i]:
			for j in range(2 * i, n + 1, i):
				isPrime[j] = False
	return isPrime
prim = Sieve(int(10000000.0) + 3)
tot_prim_nums = list(accumulate(prim))
t = int(input())
while t:
	(x, y) = map(int, input().split())
	ans = tot_prim_nums[y] - tot_prim_nums[x + 1]
	print(y - x - ans)
	t -= 1


prime = [True for i in range(int(10000000.0) + 1)]
p = 2
n = int(10000000.0)
while p * p <= n:
	if prime[p] == True:
		for i in range(p * p, n + 1, p):
			prime[i] = False
	p += 1
li = [0, 0]
c = 0
for i in range(2, int(10000000.0) + 1):
	if prime[i]:
		c += 1
	li.append(c)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(y - x - (li[y] - li[x + 1]))


n = 10000000
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p ** 2, n + 1, p):
			prime[i] = False
	p += 1
prime[0] = False
prime[1] = False
d = {0: 0, 1: 0}
count = 0
for p in range(n + 1):
	if prime[p]:
		count += 1
		d[p] = count
	else:
		d[p] = count
for t in range(int(input())):
	(X, Y) = map(int, input().split())
	total = Y - X
	ans = d[Y] - d[X]
	ans += total - ans * 2
	if prime[X + 1]:
		ans += 1
	print(ans)


from math import *
n = 10000000
primes = [True] * (n + 1)
primes[0] = False
primes[1] = False
for i in range(2, int(sqrt(n)) + 1):
	if primes[i] == True:
		for j in range(i * i, n + 1, i):
			primes[j] = False
pre_sum = [0] * (n + 1)
count = 0
for i in range(len(primes)):
	if primes[i] == True:
		count = count + 1
		pre_sum[i] = count
	else:
		pre_sum[i] = count
pre_sum[1] = 1
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	dist = y - x
	p = pre_sum[y] - pre_sum[x + 1]
	print(dist - p)


import math
from collections import Counter
from sys import stdin, stdout
input = stdin.readline
a = [1] * (10 ** 7 + 3)
a[0] = a[1] = 0
b = [0] * (10 ** 7 + 3)
for i in range(2, int(math.sqrt(10 ** 7 + 3)) + 1):
	if a[i]:
		for j in range(i * i, 10 ** 7 + 3, i):
			a[j] = 0
b = a
for i in range(1, 10 ** 7 + 3):
	b[i] += b[i - 1]
for t in range(int(input())):
	(x, y) = map(int, input().split())
	c = y - x
	d = b[y] - b[x + 1]
	print(c - d)


n = 10 ** 7 + 10
pr = [True for i in range(n)]
i = 2
while i * i < n:
	if pr[i]:
		for j in range(2 * i, n, i):
			pr[j] = False
	i += 1
dp = [0] * n
pr[0] = pr[1] = False
dp[0] = 0
dp[1] = 0
dp[2] = 1
for i in range(3, n):
	if pr[i]:
		dp[i] = 1 + dp[i - 2]
	else:
		dp[i] = 1 + dp[i - 1]
import sys
for _ in range(int(input())):
	(x, y) = map(int, sys.stdin.readline().split())
	if x == 1:
		sys.stdout.write(str(dp[y] - dp[x]) + '\n')
	elif pr[x + 1]:
		sys.stdout.write(str(dp[y] - dp[x] + 1) + '\n')
	else:
		sys.stdout.write(str(dp[y] - dp[x]) + '\n')


import sys
from math import sqrt, ceil, floor, gcd
from collections import Counter
input = lambda : sys.stdin.readline()

def int_arr():
	return list(map(int, input().split()))

def str_arr():
	return list(map(str, input().split()))

def get_str():
	return map(str, input().split())

def get_int():
	return map(int, input().split())

def get_flo():
	return map(float, input().split())

def lcm(a, b):
	return a * b // gcd(a, b)
mod = 1000000007

def generatePrime(n):
	prime = [1 for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p ** 2, n + 1, p):
				prime[i] = 0
		p += 1
	(prime[0], prime[1]) = (0, 0)
	for i in range(1, len(prime)):
		prime[i] += prime[i - 1]
	return prime
prime = generatePrime(10000008)

def solve(a, b):
	if a + 2 <= b:
		print(b - a - (prime[b] - prime[a + 1]))
	else:
		print(b - a)
for _ in range(int(input())):
	(a, b) = get_int()
	solve(a, b)


import sys
import bisect

def get_line():
	return list(map(int, sys.stdin.readline().strip().split()))

def in1():
	return int(input())

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)
a = []
SieveOfEratosthenes(10000000)
for _ in range(in1()):
	(x, y) = get_line()
	xr = bisect.bisect_right(a, x)
	yr = bisect.bisect_right(a, y) - 1
	y_minus_x = y - x
	diff_of_yr_xr = yr - xr + 1
	if a[xr] - x < 2:
		diff_of_yr_xr -= 1
	print(y_minus_x - diff_of_yr_xr)


from itertools import accumulate

def sieve_of_erothstenes(y):
	primes = [True] * (y + 1)
	primes[0] = primes[1] = False
	s = 2
	while s * s <= y:
		if primes[s]:
			for i in range(s * s, y + 1, s):
				primes[i] = False
		s += 1
	return primes
primes = list(accumulate(sieve_of_erothstenes(int(10000000.0 + 1))))
t = int(input())
while t:
	t -= 1
	(x, y) = map(int, input().strip().split())
	ans = y - x
	if x == y:
		print(0)
	elif y == x + 1:
		print(1)
	else:
		num_of_primes = primes[y] - primes[x + 1]
		ans -= num_of_primes
		print(ans)


def sieve_of_eratosthenes(n):
	arr = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if arr[p]:
			for i in range(p ** 2, n + 1, p):
				arr[i] = False
		p += 1
	arr[0] = False
	arr[1] = False
	count = 0
	prime_count = [0, 0]
	for i in range(2, n + 1):
		if arr[i]:
			count += 1
		prime_count.append(count)
	return prime_count
x_inputs = []
y_inputs = []
y_max = -1
t = int(input())
for i in range(0, t):
	(x, y) = map(int, input().split())
	x_inputs.append(x)
	y_inputs.append(y)
	if y > y_max:
		y_max = y
primes = sieve_of_eratosthenes(y_max)
for i in range(0, t):
	in_between_primes = primes[y_inputs[i]] - primes[x_inputs[i] + 1]
	steps = y_inputs[i] - x_inputs[i] - in_between_primes
	print(steps)


limit = 10000001
prime = [1 for i in range(limit + 1)]
p = 2
while p * p <= limit:
	if prime[p] == 1:
		for i in range(p ** 2, limit + 1, p):
			prime[i] = 0
	p += 1
prime[0] = 0
prime[1] = 0
ans = [0 for i in range(limit + 1)]
for i in range(2, limit + 1):
	ans[i] = ans[i - 1] + prime[i]
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if x == 1 and y == 2:
		print(1)
	elif x == 1 and y == 3:
		print(2)
	elif x == 2 and y == 3:
		print(1)
	else:
		print(y - x - ans[y] + ans[x + 1])


import sys
from collections import deque
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
test_case = 1
test_case = int(fast())
sys.setrecursionlimit(10 ** 6)
sieve = [True] * 10000009
sievenumstore = []

def dosievestuff():
	p = 2
	n = 10000009
	while p * p <= n:
		if sieve[p] == True:
			for i in range(p * p, n + 1, p):
				if i >= n:
					break
				sieve[i] = False
		p += 1
	for i in range(2, len(sieve)):
		if sieve[i]:
			sievenumstore.append(i)

def binarysearchcustom(num):
	low = 0
	high = len(sievenumstore)
	temp = -1
	while low < high:
		mid = low + (high - low) // 2
		if sievenumstore[mid] <= num:
			temp = mid
			low = mid + 1
		else:
			high = mid
	return temp
dosievestuff()
for _ in range(test_case):
	(x, y) = [int(_) for _ in fast().split()]
	intial = bisect.bisect_right(sievenumstore, x)
	lastindex = binarysearchcustom(y)
	if lastindex == -1:
		lastindex = len(sievenumstore)
	maximumjumppossible = y - x
	if abs(x - sievenumstore[intial]) > 1:
		intial -= 1
	print(maximumjumppossible - (lastindex - intial))


import io, os, time, math
from sys import stdin, stdout
from bisect import bisect_right as br, bisect_left as bl

def take_input():
	return stdin.readline()

def display_arr(arr):
	stdout.write(' '.join(map(str, arr)) + '\n')

def display_num(num):
	stdout.write(str(num) + '\n')

def sieve():
	prime = [1] * high
	p = 2
	while p * p < high:
		if prime[p] == 1:
			i = p * p
			while i < high:
				prime[i] = 0
				i += p
		p += 1
	for p in range(2, high):
		prefix[p] = prefix[p - 1]
		if prime[p] == 1:
			prefix[p] += 1

def query(l, r):
	return prefix[r] - prefix[l - 1]
high = 10 ** 7 + 1
prefix = [0] * high
sieve()
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	p_c = query(x + 2, y)
	diff = y - x
	print(diff - p_c)


import sys
from collections import deque
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
test_case = 1
test_case = int(fast())
sys.setrecursionlimit(10 ** 6)
sieve = [True] * 10000009
helper = []

def dosieve():
	p = 2
	n = 10000009
	while p * p <= n:
		if sieve[p] == True:
			for i in range(p * p, n + 1, p):
				if i >= n:
					break
				sieve[i] = False
		p += 1
	for i in range(2, len(sieve)):
		if sieve[i]:
			helper.append(i)

def binary(num):
	low = 0
	high = len(helper)
	temp = -1
	while low < high:
		mid = low + (high - low) // 2
		if helper[mid] <= num:
			temp = mid
			low = mid + 1
		else:
			high = mid
	return temp

def ans():
	(x, y) = [int(_) for _ in fast().split()]
	intial = bisect.bisect_right(helper, x)
	last = binary(y)
	if last == -1:
		last = len(helper)
	maxi = y - x
	if abs(x - helper[intial]) > 1:
		intial -= 1
	print(maxi - (last - intial))
	return
dosieve()
for _ in range(test_case):
	ans()


import math
limit = int(10000000.0) + 1
prime = [1] * limit
prime[0] = 0
prime[1] = 0
for i in range(2, int(math.sqrt(limit)) + 2):
	if prime[i]:
		for j in range(2 * i, limit, i):
			prime[j] = 0
prime_prefix_sum = prime[:]
for i in range(1, limit):
	prime_prefix_sum[i] = prime_prefix_sum[i] + prime_prefix_sum[i - 1]
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	ans = y - x
	no_of_primes = prime_prefix_sum[y - 1] - prime_prefix_sum[x]
	ans -= no_of_primes
	if prime[x + 1]:
		ans = ans + 1
	if prime[y]:
		ans = ans - 1
	print(ans)


n = 10000000
prime = [True for i in range(n + 1)]
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p ** 2, n + 1, p):
			prime[i] = False
	p += 1
prime[0] = False
prime[1] = False
lookup = {0: 0, 1: 0}
k = 0
for p in range(n + 1):
	if prime[p]:
		k += 1
		lookup[p] = k
	else:
		lookup[p] = k
for _ in range(int(input())):
	(X, Y) = map(int, input().split(' '))
	total = Y - X
	ans = lookup[Y] - lookup[X]
	ans += total - ans * 2
	if prime[X + 1]:
		ans += 1
	print(ans)


def calprimes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	primes = []
	for p in range(2, n + 1):
		if prime[p]:
			primes.append(p)
	return primes
import bisect
primes = calprimes(10000001)
t = int(input())
for t in range(t):
	(x, y) = [int(x) for x in input().split()]
	ans = y - x - (bisect.bisect(primes, y) - bisect.bisect(primes, x)) + 1 * (primes[bisect.bisect(primes, x)] - x == 1)
	print(ans)