# Original solution
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def main():
    Q = int(eval(input()))
    lr = []
    for i in range(Q):
        l, r = list(map(int,input().split()))
        lr.append((l,r))
        
    mapd = []
    for i in range(0, 100001):
        if i == 0:
            mapd.append(0)
            continue
        if i == 1:
            mapd.append(0)
            continue
        if i % 2 == 0:
            mapd.append(mapd[i-1])
            continue
        if is_prime(i) and is_prime((i+1)/2):
            mapd.append(mapd[i-1] + 1)
        else:
            mapd.append(mapd[i-1])
            
        
    for i in lr:
        l, r = i
        print((mapd[r] - mapd[l-1]))
    
def is_prime(n): 
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True
	
if __name__ == "__main__":
	main()


# Optimized solution
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
 
##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力
 
# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと
 
##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順
 
# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順
 
##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(eval(input()))
def inputMap(): return list(map(int, input().split()))
def inputList(): return list(map(int, input().split()))
 
inf = float('inf')
mod = 1000000007
 
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def main():
    Q = inputInt()
    
    total = 0
    lists = [0,0]
    for i in range(2,10**5+1):
        if i % 2 == 0:
            lists.append(total)
            continue
            
        if is_prime(i) == True and is_prime((i+1)//2) == True:
            total += 1
        lists.append(total)
        
    #print(lists)
    for i in range(Q):
        l,r = inputMap()
        #print("{} {}".format(lists[r], lists[l]))
        print((lists[r] - lists[l-1]))
    
def is_prime(n): 
    i = 2
    while i * i <=n:
        if n % i == 0:
            return False
        i += 1
    return True
     
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y
         
if __name__ == "__main__":
	main()