Chef's current score is X. Each second, Chef will find the smallest [prime factor] of his score and add it to his score.

Determine the minimum time in seconds, after which his score becomes ≥ Y.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line containing two integers X and Y, the initial and required score of Chef.

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

For each test case, output the minimum time in seconds, after which Chef's score becomes ≥ Y.

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

$1 ≤ T ≤ 1000$
$2 ≤ X ≤ 10$
$20 ≤ Y ≤ 10^{9}$

----- Sample Input 1 ------ 
4
2 23
9 20
5 100
6 89

----- Sample Output 1 ------ 
11
5
46
42

----- explanation 1 ------ 
Test case $1$: The initial score is $2$. Chef needs the score to be at least $23$. 
- The smallest prime factor of $2$ is $2$. Thus, the score increase to $2+2 = 4$.  
- The smallest prime factor of $4$ is $2$. Thus, the score increase to $4+2 = 6$.
- Similarly, each time the score would be increased by $2$. Thus, after $11$ seconds, the score becomes $24$, which is $≥ 23$.

Test case $2$: The initial score is $9$. Chef needs the score to be at least $20$. 
- The smallest prime factor of $9$ is $3$. Thus, the score increase to $9+3 = 12$.  
- The smallest prime factor of $12$ is $2$. Thus, the score increase to $12+2 = 14$.
- The smallest prime factor of $14$ is $2$. Thus, the score increase to $14+2 = 16$.
- The smallest prime factor of $16$ is $2$. Thus, the score increase to $16+2 = 18$.
- The smallest prime factor of $18$ is $2$. Thus, the score increase to $18+2 = 20$.

Thus, after $5$ seconds, the score becomes $20$, which is $≥ 20$.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
def getprime(n):
	if n <= 2:
		return n
	i = 2
	while n % i != 0 and i / 2 <= n:
		i += 1
	if i <= n // 2:
		return i
	return n
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	p = getprime(x)
	if p == 2:
		print((y - x) // p + (y - x) % p)
	elif p % 2 == 1 and x % 2 == 1:
		x += p
		p = 2
		print((y - x) // p + (y - x) % p + 1)


def prime(x):
	i = 2
	while x % i != 0:
		i += 1
	return i
for i in range(int(input())):
	(x, y) = map(int, input().split())
	p = prime(x)
	if p == 2:
		print((y - x) // 2 + (y - x) % 2)
	elif x % 2 == 1:
		x = x + p
		print(1 + (y - x) % 2 + (y - x) // 2)


import math

def leastPrimeFactor(n):
	least_prime = [0] * (n + 1)
	least_prime[1] = 1
	for i in range(2, n + 1):
		if least_prime[i] == 0:
			least_prime[i] = i
			for j in range(i * i, n + 1, i):
				if least_prime[j] == 0:
					least_prime[j] = i
	return least_prime[n]
for _ in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	if x % 2 == 0:
		print(math.ceil((y - x) / 2))
	else:
		temp = leastPrimeFactor(x)
		x = x + temp
		print(math.ceil((y - x) / 2) + 1)


t = int(input())
for i in range(t):
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	cnt = 0
	if x >= y:
		print('0')
	elif x % 2 == 0:
		diff = y - x
		if diff % 2 == 0:
			print(cnt + diff // 2)
		else:
			print(cnt + 1 + diff // 2)
	else:
		diff = 0
		while x < y:
			if x % 2 == 0:
				diff = y - x
				r = -1
				break
			elif x % 3 == 0:
				diff = y - x
				x += 3
				cnt += 1
			elif x % 5 == 0:
				diff = y - x
				x += 5
				cnt += 1
			elif x % 7 == 0:
				diff = y - x
				x += 7
				cnt += 1
			elif x % 11 == 0:
				diff = y - x
				x += 11
				cnt += 1
			elif x % 13 == 0:
				diff = y - x
				x += 13
				cnt += 1
			else:
				diff = y - x
				x += 17
				cnt += 1
		if r == -1:
			if diff % 2 == 0:
				print(cnt + diff // 2)
			else:
				print(cnt + 1 + diff // 2)
		else:
			print(cnt)


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	i = 0
	while x < y:
		if x % 2 == 0:
			i += (y - x) // 2 if (y - x) % 2 == 0 else (y - x) // 2 + 1
			break
		elif x % 3 == 0:
			x += 3
		elif x % 5 == 0:
			x += 5
		elif x % 7 == 0:
			x += 7
		i += 1
	print(i)


def prime(n):
	f = 0
	for i in range(2, n):
		if n % i == 0:
			f = 1
	if n == 2:
		p = True
	elif f == 0:
		p = True
	else:
		p = False
	return p
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	s = 0
	for i in range(2, x + 1):
		if x % i == 0 and prime(i):
			s = s + 1
			x = x + i
			break
	if y % 2 == 0:
		print(int((y - x) / 2 + 1))
	else:
		print(int((y + 1 - x) / 2 + 1))


def least_prime(n):
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return i
	return n
for i in range(int(input())):
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		if y % 2 == 0:
			print(int((y - x) / 2))
		else:
			print(int((y - x) / 2 + 1))
	else:
		z = least_prime(x)
		x = x + z
		if y % 2 == 0:
			print(int((y - x) / 2 + 1))
		else:
			print(int((y - x) / 2 + 2))


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	num = x
	sec = 0
	if x % 2:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				x += i
				break
		else:
			x *= 2
		sec += 1
	if x >= y:
		print(1)
	elif (y - x) % 2 == 0:
		print(sec + (y - x) // 2)
	else:
		print(sec + (y - x) // 2 + 1)


import math
for t in range(int(input())):
	(x, y) = map(int, input().split())
	ans = 0
	y -= x
	if x % 2 == 0:
		ans = math.ceil(y / 2)
	elif x % 3 == 0:
		ans += 1
		y -= 3
		ans += math.ceil(y / 2)
	elif x % 5 == 0:
		ans += 1
		y -= 5
		ans += math.ceil(y / 2)
	elif x % 7 == 0:
		ans += 1
		y -= 7
		ans += math.ceil(y / 2)
	print(ans)


import math

def prFactor(inp):
	if inp % 2 == 0:
		return 2
	if inp == 9:
		return 3
	if inp == 3:
		return 3
	if inp == 5:
		return 5
	if inp == 7:
		return 7
cases = eval(input())
while cases > 0:
	count = 0
	val = input().split(' ')
	isc = int(val[0])
	nsc = int(val[1])
	while isc % 2 != 0:
		isc = isc + prFactor(isc)
		count = count + 1
	runr = nsc - isc
	val = runr / 2
	c = math.ceil(count + val)
	print(c)
	cases = cases - 1


import math as M
t = int(input())
for _ in range(t):
	(x, y) = list(map(int, input().split()))
	need = y - x
	if x % 2 == 0:
		print(int(M.ceil(need / 2)))
	elif x == 9:
		need -= 3
		print(int(M.ceil(need / 2)) + 1)
	else:
		need -= x
		print(int(M.ceil(need / 2)) + 1)


import math
t = int(input())

def solve():
	(x, y) = [int(i) for i in input().split()]
	if x % 2 == 0:
		print(math.ceil((y - x) / 2))
	elif x == 9:
		print(math.ceil((y - (x + 3)) / 2 + 1))
	else:
		print(math.ceil((y - (x + x)) / 2 + 1))
for i in range(t):
	{solve()}


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	for i in range(2, x + 1):
		if x % i == 0:
			x += i
			break
	n = y - x
	if n % 2 == 1:
		n += 1
	n = n // 2
	print(n + 1)


for _ in range(int(input())):
	(x, y) = map(int, input().strip().split())
	if x % 2 == 0:
		x += 2
	elif x % 3 == 0:
		x += 3
	elif x % 5 == 0:
		x += 5
	elif x % 7 == 0:
		x += 7
	print(1 + int((y - x) / 2) + (y - x) % 2)


import math

def spf(a):
	x = 3
	while x <= math.sqrt(a):
		if a % x == 0:
			return x
		x += 1
	return a
for i in range(int(input())):
	a = list(map(int, input().split()))
	(x, y) = (a[0], a[1])
	if x % 2 == 0:
		print(math.ceil((y - x) / 2))
	else:
		c = spf(x)
		print(math.ceil((y - (x + c)) / 2) + 1)


import math
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	res = x
	count = 0
	if x % 2 == 0:
		cnt = y - x
		count += int(math.ceil(cnt / 2))
	else:
		if x == 3 or x == 9:
			x = x + 3
			count += 1
		else:
			x = x + x
			count += 1
		cnt = y - x
		count += int(math.ceil(cnt / 2))
	print(count)


import math as m
for _ in range(int(input())):
	(n, t) = map(int, input().split())
	if n % 2 == 0:
		d = t - n
		print(int(m.ceil(d / 2)))
	elif n != 9:
		d = t - n * 2
		print(int(m.ceil(d / 2)) + 1)
	else:
		d = t - n - 3
		print(int(m.ceil(d / 2)) + 1)


for t in range(int(input())):
	(a, b) = map(int, input().split())
	if a % 2 == 0:
		print((b - a + 1) // 2)
	elif a == 9:
		b = b - 3
		print((b - a + 1) // 2 + 1)
	else:
		b = b - a
		print((b - a + 1) // 2 + 1)


from collections import defaultdict
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		dif = y - x
		cnt = dif // 2
		if dif % 2 == 1:
			cnt += 1
		print(cnt)
		continue
	prime = [0] * (10 ** 6 + 1)
	d = defaultdict(int)
	for i in range(2, 10 ** 4 + 1):
		if prime[i] == 0:
			d[i] = i
			p = i * i
			while p * p <= 10 ** 4:
				prime[p] = 1
				d[p] = i
				p += i
	cnt = 0
	while x < y and x % 2 == 1:
		x += d[x]
		cnt += 1
	if x < y:
		dif = y - x
		cnt += dif // 2
		if dif % 2 == 1:
			cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		print((y - x + 1) // 2)
	elif x == 9:
		y = y - 3
		print((y - x + 1) // 2 + 1)
	else:
		y = y - x
		print((y - x + 1) // 2 + 1)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	c = 0
	while x < y:
		if x % 2 == 0:
			print(c + math.ceil((y - x) / 2))
			break
		elif x % 3 == 0:
			x += 3
			c += 1
		elif x % 5 == 0:
			x += 5
			c += 1
		elif x % 7 == 0:
			x += 7
			c += 1
		elif x % 9 == 0:
			x += 9
			c += 1


from math import ceil

def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		print(ceil((y - x) / 2))
	elif x == 3:
		print(ceil((y - x - 3) / 2 + 1))
	elif x % 3 == 0:
		print(ceil((y - x - 3) / 2 + 1))
	elif isPrime(x):
		print(ceil((y - 2 * x) / 2 + 1))


def factor(n):
	for i in range(2, n + 1):
		if n % i == 0:
			return i

def odev(n):
	if n % 2 == 0:
		return 1
	else:
		return 0
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	k = factor(a)
	c = (b - a - k) // 2
	if odev(b):
		print(c + 1)
	else:
		print(c + 2)


def smallest_prime_factor(n):
	for i in range(2, n + 1):
		if n % i == 0:
			return i
t = int(input())
for cases in range(t):
	(x, y) = map(int, input().split(' '))
	time = 0
	if x % 2 == 1:
		x += smallest_prime_factor(x)
		time += 1
	print(time + (y - x + 1) // 2)


t = int(input())
time = 0
for i in range(t):
	(x, y) = map(int, input().split())
	for j in range(2, x + 1):
		if x % j == 0:
			x += j
			time = 1
			break
	if y % 2 == 0:
		time += (y - x) // 2
	else:
		time += (y - x + 1) // 2
	print(time)


import math
for i in range(int(input())):
	(x, y) = map(int, input().split())
	k = y - x
	if x % 2 == 0:
		print(math.ceil(k / 2))
	elif x == 9:
		k -= 3
		print(math.ceil(k / 2) + 1)
	else:
		k -= x
		print(math.ceil(k / 2) + 1)


def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return i
	return n

def Answer():
	(x, y) = map(int, input().split())
	x += smallestDivisor(x)
	print(1 + (y - x + 1) // 2)
t = int(input())
for i in range(t):
	Answer()


for _ in range(int(input())):
	(x, y) = [int(i) for i in input().split()]
	t = 0
	if not x % 2 == 0:
		t = 1
		for j in range(3, x + 1):
			if x % j == 0:
				x += j
				break
	print((y - x) // 2 + (y - x) % 2 + t)


def prime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
import math
for _ in range(int(input())):
	c = 0
	(a, b) = map(int, input().split())
	if a % 2 == 0:
		print(math.ceil((b - a) / 2))
	else:
		i = 3
		while a < b:
			if a % 2 == 0:
				c += math.ceil((b - a) / 2)
				break
			elif a % i == 0 and prime(i):
				a += i
				i = 3
				c += 1
			else:
				i += 2
		print(c)


import math
t = int(input())
while t:
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		op = math.ceil((y - x) / 2)
	else:
		if x % 3 == 0:
			x += 3
		elif x % 5 == 0:
			x += 5
		elif x % 7 == 0:
			x += 7
		op = math.ceil((y - x) / 2) + 1
	print(op)
	t -= 1


from math import *

def smalldiv(a):
	for i in range(2, int(sqrt(a)) + 1):
		if a % i == 0:
			return i
	return a
for i in range(int(input())):
	(x, y) = map(int, input().split())
	count = 0
	while x < y:
		if x % 2 == 0:
			if (y - x) % 2 == 0:
				count += int((y - x) / 2)
				break
			else:
				count += int((y - x + 1) / 2)
				break
		else:
			d = smalldiv(x)
			x += d
			count += 1
	print(count)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	for i in range(2, x + 1):
		if x % i == 0:
			x = x + i
			break
	k = math.ceil((y - x) / 2)
	print(k + 1)


T = int(input(''))
for i in range(T):
	(X, Y) = map(int, input().split())
	if X % 2 == 0:
		if Y % 2 == 0:
			print(int((Y - X) / 2))
		else:
			print(int((Y - X) / 2 + 1))
	elif X % 3 == 0:
		X = X + 3
		if Y % 2 == 0:
			print(int((Y - X) / 2 + 1))
		else:
			print(int((Y - X) / 2 + 2))
	elif X % 5 == 0:
		X = X + 5
		if Y % 2 == 0:
			print(int((Y - X) / 2 + 1))
		else:
			print(int((Y - X) / 2 + 2))
	elif X == 7:
		X = X + 7
		if Y % 2 == 0:
			print(int((Y - X) / 2 + 1))
		else:
			print(int((Y - X) / 2 + 2))


def findprime(n):
	for i in range(2, n + 1):
		if n % i == 0:
			return i
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a % 2 == 0:
		print((b - a + 1) // 2)
	else:
		count = 0
		while a < b:
			x = findprime(a)
			if x == 2:
				count += (b - a + 1) // 2
				break
			else:
				a += x
				count += 1
		print(count)


import math
t = int(input())
for tc in range(t):
	(x, y) = map(int, input().split())
	n = y - x
	v = 0
	if x % 2 == 0:
		v = int(math.ceil(n / 2))
	elif x == 9:
		n -= 3
		v = int(math.ceil(n / 2) + 1)
	else:
		n -= x
		v = int(math.ceil(n / 2) + 1)
	print(v)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	count = 0
	while x % 2 != 0:
		for i in range(3, x + 1):
			if x % i == 0:
				x += i
				count += 1
				break
	ans = count + (y - x) // 2
	print(ans + 1 if y % 2 != 0 else ans)


def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	res = 0
	while x < y:
		x = x + smallestDivisor(x)
		res += 1
		if x % 2 == 0:
			break
	res += (y - x) // 2
	if y % 2 == 1:
		print(res + 1)
	else:
		print(res)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(10000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def dfs(n, k):
	need = k - n
	if n % 2 == 0:
		return math.ceil(need / 2)
	elif n == 9:
		need -= 3
		return math.ceil(need / 2) + 1
	else:
		need -= n
		return math.ceil(need / 2) + 1
tried = int(input())
for _ in range(tried):
	(n, k) = mul()
	print(dfs(n, k))


for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	f = 0
	while x < y:
		if x % 2 == 0:
			print((y - x) // 2 + y % 2 + f)
			break
		else:
			f = 1
			for i in range(3, x // 2 + 1):
				if x % i == 0:
					x += i
					break
			else:
				x += x


import math

def prime(num):
	for i in range(2, int(round(num / 2 + 1))):
		if num % i == 0:
			return i
	return num
num_test = int(input())
for i in range(0, num_test):
	(num, y) = map(int, input().split())
	min_num = int(prime(num))
	count = num + min_num
	sun = 1
	if math.floor((y - count) / 2) < (y - count) / 2:
		sun += math.floor((y - count) / 2) + 1
	else:
		sun += math.floor((y - count) / 2)
	print(sun)


t = int(input())
while t != 0:
	t = t - 1
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		print((y - x + 1) // 2)
	elif x == 7:
		print(1 + (y - 7 - x + 1) // 2)
	elif x == 5:
		print(1 + (y - 5 - x + 1) // 2)
	else:
		print(1 + (y - 3 - x + 1) // 2)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		print(math.ceil((y - x) / 2))
	else:
		for i in [3, 5, 7]:
			if x % i == 0:
				x = x + i
				break
		print(math.ceil((y - x) / 2) + 1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	x = n
	c = 0
	while x < m:
		if x % 2 == 0:
			if (m - x) % 2 == 1:
				c = c + (m - x) // 2 + 1
				break
			else:
				c = c + (m - x) // 2
				break
		for j in range(2, x + 1):
			if x % j == 0:
				x = x + j
				break
		c = c + 1
	print(c)


from collections import *
from bisect import *
from heapq import *
from math import *
import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	cnt = 0
	while x < y:
		cnt += 1
		if x % 2 == 0:
			rem = y - x
			if (y - x) % 2:
				cnt += (y - x) // 2 + 1
				x += (y - x) // 2 * 2 + 2
			else:
				cnt += (y - x) // 2
				x += (y - x) // 2 * 2
			cnt -= 1
			continue
		xx = x
		for i in range(2, int(x ** 0.5) + 1):
			if x % i == 0:
				x += i
				break
		if xx == x:
			x += x
	print(cnt)


t = int(input())
tb = []
for nn in range(0, t):
	jj = str(input())
	vv = jj.split(' ')
	jnb = []
	for ii in vv:
		jnb.append(int(ii))
	tb.append(jnb)
for xxz in tb:
	score = xxz[0]
	target = xxz[1]
	ite = 0
	if score % 2 != 0:
		ite = 1
		for tth in range(3, score + 1, 2):
			if score % tth == 0:
				score += tth
				break
		if score >= target:
			print(ite)
		elif target % 2 == 0:
			hbv = target - score
			print(ite + hbv // 2)
		else:
			hbv = target - 1 - score
			print(hbv // 2 + 1 + ite)
	elif target % 2 == 0:
		hbv = target - score
		print(hbv // 2)
	else:
		hbv = target - 1 - score
		print(hbv // 2 + 1)


import math
t = int(input())
while t:
	(x, y) = map(int, input().split())
	i = 0
	while x < y:
		if x % 2 == 0:
			i += math.ceil((y - x) / 2)
			break
			x += 2
		elif x % 3 == 0:
			x += 3
		elif x % 5 == 0:
			x += 5
		elif x % 7 == 0:
			x += 7
		i += 1
	print(i)
	t -= 1


import math
T = int(input())
for i in range(T):
	(X, Y) = input().split()
	X = int(X)
	Y = int(Y)
	if X % 2 == 0:
		print(math.ceil((Y - X) / 2))
	elif X == 3:
		if Y <= 6:
			print(1)
		else:
			print(1 + math.ceil((Y - 6) / 2))
	elif X == 5:
		if Y <= 10:
			print(1)
		else:
			print(1 + math.ceil((Y - 10) / 2))
	elif X == 7:
		if Y <= 14:
			print(1)
		else:
			print(1 + math.ceil((Y - 14) / 2))
	elif Y <= 12:
		print(1)
	else:
		print(1 + math.ceil((Y - 12) / 2))


fuck = int(input())
while fuck > 0:
	a = list(map(int, input().split()))
	count = 0
	g = False
	if a[0] % 2 == 0:
		g = True
	while a[0] < a[1]:
		if a[0] % 2 == 0:
			b = a[1] - a[0]
			if b % 2 == 0:
				count = int(b / 2)
				a[0] = a[1]
				break
			else:
				count = int((b + 1) / 2)
				a[0] = a[1]
				break
		else:
			i = 2
			flag = False
			while i * i <= a[0]:
				if a[0] % i == 0:
					a[0] += i
					count += 1
					flag = True
					i = a[0]
				i += 1
			if flag == False:
				a[0] += a[0]
				count += 1
				flag = False
	if g == True:
		print(count)
	else:
		print(count + 1)
	fuck -= 1


import math

def prime(num):
	for i in range(2, math.floor(num ** 0.5 + 1)):
		if num % i == 0:
			return False
	return True

def lprime(score):
	for i in range(2, math.floor(score ** 0.5 + 1)):
		if score % i == 0 and prime(i):
			return i
	return score
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	score = x
	t = 0
	l = []
	for i in range(2, math.floor(score ** 0.5 + 1)):
		if prime(i):
			l.append(i)
	l.append(score)
	while score < y:
		if score % 2 == 0:
			t += (y - score) // 2 + y % 2
			break
		for i in l:
			if score % i == 0:
				score += i
				break
		t += 1
	print(t)


T = int(input())
for i in range(T):
	a = input()
	(X, Y) = [int(i) for i in a.split(' ')]
	time = 0
	fact = -1
	for i in range(2, int(X ** 0.5) + 1):
		if X % i == 0:
			fact = i
			break
	if fact == -1:
		fact = X
	X = X + fact
	if (Y - X) % 2 == 0:
		print(int((Y - X) / 2 + 1))
	else:
		print(int((Y - X) // 2 + 2))


t = int(input())
for i in range(t):
	(x, y) = input().split()
	(x, y) = (int(x), int(y))
	a = int(0)
	if x % 2 == 0:
		if y % 2 == 0:
			a = int((y - x) / 2)
		else:
			a = int((y - x) / 2) + 1
	elif x % 3 == 0:
		x += 3
		if x >= y:
			a = 1
		elif y % 2 == 0:
			a = int((y - x) / 2 + 1)
		else:
			a = int((y - x) / 2) + 2
	elif x % 5 == 0:
		x += 5
		if x >= y:
			a = 1
		elif y % 2 == 0:
			a = int((y - x) / 2 + 1)
		else:
			a = int((y - x) / 2) + 2
	elif x % 7 == 0:
		x += 7
		if x >= y:
			a = 1
		elif y % 2 == 0:
			a = int((y - x) / 2 + 1)
		else:
			a = int((y - x) / 2) + 2
	print(a)


def smallPrime(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n
try:
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		ans = 0
		while a < b:
			a += smallPrime(a)
			ans += 1
			if a % 2 == 0:
				break
		c = 0
		if (b - a) % 2 == 0:
			c = (b - a) // 2
		else:
			c = (b - a) // 2 + 1
		print(ans + c)
except:
	pass


import math
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		print(math.ceil(y / 2) - x // 2)
	else:
		res = math.ceil(y / 2)
		if x == 3:
			print(res - x + 1)
		elif x == 5:
			print(res - x + 1)
		elif x == 7:
			print(res - x + 1)
		else:
			print(res - 5)


import math
T = int(input())
for i in range(T):
	i = input()
	(X, Y) = i.split()
	(X, Y) = (int(X), int(Y))
	second_count = 0
	if X % 2 == 0:
		print(math.ceil((Y - X) / 2))
	else:
		for i in range(2, X + 1):
			if X % i == 0:
				X += i
				break
		print(1 + math.ceil((Y - X) / 2))


def smallest_factor(x):
	for i in range(2, 8):
		if x % i == 0:
			return i
			break
	return x
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	res = 0
	while x < y:
		if x % 2 == 0:
			if (y - x) % 2 == 0:
				res += (y - x) // 2
			else:
				res += (y - x) // 2 + 1
			break
		else:
			x += smallest_factor(x)
		res += 1
	print(res)


import math
for tc in range(int(input())):
	(X, Y) = map(int, input().split(' '))
	if X % 2 == 0:
		print(math.ceil((Y - X) / 2))
	elif X % 3 == 0:
		print(math.ceil((Y - X - 3) / 2 + 1))
	elif X % 5 == 0:
		print(math.ceil((Y - X - 5) / 2 + 1))
	else:
		print(math.ceil((Y - X - 7) / 2 + 1))


import math as m
for i in range(int(input())):
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		print(m.ceil((y - x) / 2))
	elif x % 3 == 0:
		x += 3
		print(m.ceil((y - x) / 2) + 1)
	elif x % 5 == 0:
		x += 5
		print(m.ceil((y - x) / 2) + 1)
	else:
		x += x
		print(m.ceil((y - x) / 2) + 1)


T = int(input())
for i in range(T):
	(X, Y) = map(int, input().split())
	if X % 2 == 0:
		primefactor = 2
	elif X % 3 == 0:
		primefactor = 3
	else:
		primefactor = X
	X = X + primefactor
	diff = Y - X
	ans = diff // 2
	if diff % 2 != 0:
		ans += 1
	print(ans + 1)


from math import ceil

def smallest_factor(num):
	if num % 2 == 0:
		return 2
	i = 3
	while True:
		if num % i == 0:
			return i
		else:
			i += 2
test_cases = int(input())
while test_cases:
	str = input()
	(a, b) = str.split(' ')
	x = int(a)
	y = int(b)
	sec = 0
	if x % 2 == 0:
		sec = ceil((y - x) / 2)
		x += smallest_factor(x)
	else:
		sec = 1
		sec += ceil((y - x - smallest_factor(x)) / 2)
	print(sec)
	test_cases -= 1


from math import ceil
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	ans = 0
	if x & 1:
		fac = x
		for i in range(2, x + 1):
			if x % i == 0:
				fac = i
				break
		x += fac
		ans += 1
	ans += ceil((y - x) / 2)
	print(ans)


T = int(input())
for i in range(T):
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		x = x + 2
	elif x % 3 == 0:
		x = x + 3
	elif x % 5 == 0:
		x = x + 5
	else:
		x = x + 7
	if y % 2 == 1:
		y = y + 1
	diff = y - x
	count = 1 + int(diff / 2)
	print(count)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	n = b - a
	if a % 2 == 0:
		print(int(math.ceil(n / 2)))
	elif a == 9:
		n -= 3
		print(int(math.ceil(n / 2)) + 1)
	else:
		n -= a
		print(int(math.ceil(n / 2)) + 1)


import math

def smallest_prime(n):
	for i in range(2, 10):
		if n % i == 0:
			return i
for i in range(int(input())):
	(x, y) = map(int, input().split())
	t = 0
	while x <= y:
		prime = smallest_prime(x)
		if prime == 2:
			t += math.ceil((y - x) / 2)
			break
		x += prime
		t += 1
	print(t)


def sd(n):
	if n % 2 == 0:
		return 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		if n % i == 0:
			return i
	return n
n = int(input())
r = 0
for i in range(n):
	(x, y) = map(int, input().split())
	x = x + sd(x)
	r = (y - x + 1) // 2
	print(1 + r)


import math
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	li = [1, 3, 5, 7]
	ans = 0
	if x in li:
		x += x
		ans += 1
	elif x == 9:
		x += 3
		ans += 1
	else:
		x += 2
		ans += 1
	d = (y - x) / 2
	e = math.ceil(d)
	print(ans + e)


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a % 2 == 0:
		if b % 2 == 0:
			print(int((b - a) // 2))
		else:
			print(int((b - a) // 2) + 1)
	else:
		for j in range(2, int(math.sqrt(a)) + 1):
			if a % j == 0:
				c = b - a - 3
				if c // 2 == c / 2:
					print(int(c // 2) + 1)
				else:
					print(int(c // 2) + 2)
				break
		else:
			c = b - a - a
			if c // 2 == c / 2:
				print(int(c / 2) + 1)
			else:
				print(int(c / 2) + 2)


for cases in range(int(input())):
	(X, Y) = map(int, input().split())
	sec = 0
	while X < Y:
		if X % 2 == 0:
			sec += (Y - X) // 2 if (Y - X) % 2 == 0 else (Y - X) // 2 + 1
			break
		elif X % 3 == 0:
			X += 3
		elif X % 5 == 0:
			X += 5
		elif X % 7 == 0:
			X += 7
		sec += 1
	print(sec)