local function reada(n,m)m=m or 1 r={}for i=1,m do r[i]={}end for i=1,n do for j=1,m do r[j][i]=io.read"*n"end end return unpack(r)end
local function b_search(t,k,min,max)
	if(min>max)then return -1 end
	local mid=min+math.floor((max-min)/2)
	if(t[mid]>k)then return b_search(t,k,min,mid-1)
	elseif(t[mid]<k)then return b_search(t,k,mid+1,max)
	else return mid
	end
end
local function b_search2(t,k,min,max)
	if(min>max)then return min end
	local mid=min+math.floor((max-min)/2)
	if(t[mid]>k)then return b_search2(t,k,min,mid-1)
	elseif(t[mid]<k)then return b_search2(t,k,mid+1,max)
	else return mid
	end
end

Q=io.read"*n"
l,r=reada(Q,2)

a={2}
for i=3,200000,2 do
	table.insert(a,i)
end

for i=3,math.sqrt(200000),2 do
	local b={}
	for _,v in ipairs(a)do
		if(v%i~=0 or v==i)then table.insert(b,v)end
	end
	a=b
end

for i=1,Q do
	local j=b_search2(a,l[i],1,#a)
	local s=0
	while(a[j]<=r[i])do
		if(b_search(a,(a[j]+1)/2,1,#a)~=-1)then
			s=s+1
		end
		j=j+1
	end
	print(s)
end