q=int(input())
for i in range(q):
	L,R=map(int,input().split())
	cnt = 0
	a = [0] * (R+1)
	i = L
	while i <= R:
		if a[i] == 1:
			i += 1
			continue
		else:
			cnt += 1
			v = 2*i
			while v <= R:
				a[v] = 1
				v += i
			i += 1
			continue
	print(cnt)