# -*- 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()

# -*- 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()

# -*- 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()

# -*- 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()

-import copy -import collections +import math +import collections +import copy +import heapq -import math +import itertools -# NO, PAY-PAY -# import numpy as np -# import statistics -# from statistics import mean, median,variance,stdev +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 +# -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- -    Q = int(eval(input())) -    lr = [] +    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) -        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])) +        l, r = inputMap() +        # print("{} {}".format(lists[r], lists[l])) +        print((lists[r] - lists[l - 1])) +# -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- +# 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 + +