def check(i):

    num=int(i**0.5)

    if i==1:return 0

    if i==2:return 1

    for j in range(2,num+1):

        if i%j==0:break



    else:return 1

    return 0

q=int(eval(input()))

lr=[list(map(int,input().split())) for i in range(q)]



L=[0]*(10**5+1)#0~100000

for i in range(10**5+1):

    if i%2==0:

        L[i]=L[i-1]

    else:

        L[i]=L[i-1]+check(i)*check((i+1)//2)



for l,r in lr:

    cnt=L[r]-L[l-1]

    print(cnt)
def check_prime(k):

    '''

    素数の時1、合成数の時0を返す

    '''

    if k == 1:return 0

    num = int(k ** 0.5 // 1)

    for i in range(2, num + 1):

        if k % i == 0:return 0

    return 1



q = int(eval(input()))

lr = []

l_min = 10 ** 9

r_max = 0

for i in range(q):

    l, r = list(map(int,input().split()))

    lr.append((l, r))

    if l < l_min:l_min = l

    if r > r_max:r_max = r



pre_cal = [0] * (r_max - l_min + 2)

dic = {}#一度素数と判定したもの

for num in range(l_min, r_max + 1):

    pre_cal[num - l_min + 1] = pre_cal[num - l_min]

    if num % 2 == 0:continue

    if not check_prime(num):continue

    dic[num] = 1

    temp = (num + 1) // 2



    if dic.get(temp, 0):

        pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1

    else:

        if check_prime(temp):

            dic[temp] = 1

            pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1



for l, r in lr:

    ans = pre_cal[r - l_min + 1] - pre_cal[l - l_min]

    print(ans)



#print(pre_cal)
def check(i):
    num = int(i**0.5)
    if i == 1:
        return 0
    if i == 2:
        return 1
    for j in range(2, num + 1):
        if i % j == 0:
            break
    else:
        return 1
    return 0


q = int(eval(input()))
lr = [list(map(int, input().split())) for i in range(q)]
L = [0] * (10**5 + 1)  # 0~100000
for i in range(10**5 + 1):
    if i % 2 == 0:
        L[i] = L[i - 1]
    else:
        L[i] = L[i - 1] + check(i) * check((i + 1) // 2)
for l, r in lr:
    cnt = L[r] - L[l - 1]
    print(cnt)

def check_prime(k):
    """
    素数の時1、合成数の時0を返す
    """
    if k == 1:
        return 0
    num = int(k**0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:
            return 0
    return 1


q = int(eval(input()))
lr = []
l_min = 10**9
r_max = 0
for i in range(q):
    l, r = list(map(int, input().split()))
    lr.append((l, r))
    if l < l_min:
        l_min = l
    if r > r_max:
        r_max = r
pre_cal = [0] * (r_max - l_min + 2)
dic = {}  # 一度素数と判定したもの
for num in range(l_min, r_max + 1):
    pre_cal[num - l_min + 1] = pre_cal[num - l_min]
    if num % 2 == 0:
        continue
    if not check_prime(num):
        continue
    dic[num] = 1
    temp = (num + 1) // 2
    if dic.get(temp, 0):
        pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1
    else:
        if check_prime(temp):
            dic[temp] = 1
            pre_cal[num - l_min + 1] = (
                pre_cal[num - l_min + 1] + 1 if num != l_min else 1
            )
for l, r in lr:
    ans = pre_cal[r - l_min + 1] - pre_cal[l - l_min]
    print(ans)
# print(pre_cal)

-def check(i): -    num = int(i**0.5) -    if i == 1: +def check_prime(k): +    """ +    素数の時1、合成数の時0を返す +    """ +    if k == 1: -    if i == 2: -        return 1 -    for j in range(2, num + 1): -        if i % j == 0: -            break -    else: -        return 1 -    return 0 +    num = int(k**0.5 // 1) +    for i in range(2, num + 1): +        if k % i == 0: +            return 0 +    return 1 -lr = [list(map(int, input().split())) for i in range(q)] -L = [0] * (10**5 + 1)  # 0~100000 -for i in range(10**5 + 1): -    if i % 2 == 0: -        L[i] = L[i - 1] +lr = [] +l_min = 10**9 +r_max = 0 +for i in range(q): +    l, r = list(map(int, input().split())) +    lr.append((l, r)) +    if l < l_min: +        l_min = l +    if r > r_max: +        r_max = r +pre_cal = [0] * (r_max - l_min + 2) +dic = {}  # 一度素数と判定したもの +for num in range(l_min, r_max + 1): +    pre_cal[num - l_min + 1] = pre_cal[num - l_min] +    if num % 2 == 0: +        continue +    if not check_prime(num): +        continue +    dic[num] = 1 +    temp = (num + 1) // 2 +    if dic.get(temp, 0): +        pre_cal[num - l_min + 1] = pre_cal[num - l_min + 1] + 1 if num != l_min else 1 -        L[i] = L[i - 1] + check(i) * check((i + 1) // 2) +        if check_prime(temp): +            dic[temp] = 1 +            pre_cal[num - l_min + 1] = ( +                pre_cal[num - l_min + 1] + 1 if num != l_min else 1 +            ) -    cnt = L[r] - L[l - 1] -    print(cnt) +    ans = pre_cal[r - l_min + 1] - pre_cal[l - l_min] +    print(ans) +# print(pre_cal)