import math as m



def judge_prime(num):

    isPrime = [True]*(num+1)

    isPrime[0] = False

    isPrime[1] = False

    border = m.sqrt(num)

    i = 2

    while i <= border:

        if isPrime[i]:

            j = i*2

            while j <= num:

                isPrime[j] = False

                j += i

        i += 1

        

    #prime_list = []

    like2017_list = []

    for prime in range(3,num+1,2):

#        if isPrime[prime]:

#            prime_list.append(prime)

        if isPrime[int(prime)] and isPrime[int((prime+1)/2)]:

            like2017_list.append(prime)

        

    return like2017_list

        

    

    

def main():

    #input

#    Q1 = 1

#    LR1 = [[3,7]]

#    

#    Q2 = 4

#    LR2 = [[13, 13],

#                [7, 11],

#                [7, 11],

#                [2017, 2017]]

#    

#    

#    Q = Q2

#    LR = LR2

    

    Q = int(eval(input()))

    LR = []

    for i in range(Q):

        LR.append(list(map(int, input().split())))



    # 1. find 2017-like number

    MAX_Q = 10**5

    

    like2017_list = judge_prime(MAX_Q)



    

    # judge

    csum = [0]*(MAX_Q+1)

    i = 0

    cnt = 0

    for like2017 in like2017_list:

        while i < like2017:

            csum[i] = cnt

            i += 1

        cnt += 1

    for i in range(like2017_list[-1], MAX_Q+1):

        csum[i] = cnt

        

    

    for i in range(Q):

        print((csum[LR[i][1]] - csum[LR[i][0]-1]))





    

if __name__ == "__main__":

    main()
import sys

stdin = sys.stdin



sys.setrecursionlimit(10**5) 

 

def li(): return list(map(int, stdin.readline().split()))

def li_(): return [int(x)-1 for x in stdin.readline().split()]

def lf(): return list(map(float, stdin.readline().split()))

def ls(): return stdin.readline().split()

def ns(): return stdin.readline().rstrip()

def lc(): return list(ns())

def ni(): return int(stdin.readline())

def nf(): return float(stdin.readline())



from math import sqrt

from bisect import bisect_left, bisect_right



# 半開区間[lower, upper)の素数のリストを作成する

def make_prime_list(lower:int, upper:int) -> list:

    

    # 素数リストの初期化    

    isPrime = [True]*upper

    primeList = []

    

    # 区間内の数字が0,1のみならここで終了

    if upper <= 2:

        return primeList

    

    # 区間内の数字に2以上のものがあるとき

    isPrime[0] = False

    isPrime[1] = False

    

    # エラトステネスの篩の処理

    for n in range(2,int(sqrt(upper))+2):

        if isPrime[n]:

            res=2*n

            while res<upper:

                isPrime[res] = False

                res += n

    

    # 区間内の素数を抽出

    for n in range(lower,upper):

        if isPrime[n]:

            primeList.append(n)

        

    return primeList



q = ni()

query = [tuple(li()) for _ in range(q)]



prime_list = set(make_prime_list(2,10**5+1))



like2017 = []



for i in range(3, 10**5, 2):

    if (i in prime_list) and ((i+1)//2 in prime_list):

        like2017.append(i)

        

for l,r in query:

    print((bisect_right(like2017, r) - bisect_left(like2017, l)))

    
import math as m


def judge_prime(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = False
    isPrime[1] = False
    border = m.sqrt(num)
    i = 2
    while i <= border:
        if isPrime[i]:
            j = i * 2
            while j <= num:
                isPrime[j] = False
                j += i
        i += 1
    # prime_list = []
    like2017_list = []
    for prime in range(3, num + 1, 2):
        #        if isPrime[prime]:
        #            prime_list.append(prime)
        if isPrime[int(prime)] and isPrime[int((prime + 1) / 2)]:
            like2017_list.append(prime)
    return like2017_list


def main():
    # input
    #    Q1 = 1
    #    LR1 = [[3,7]]
    #
    #    Q2 = 4
    #    LR2 = [[13, 13],
    #                [7, 11],
    #                [7, 11],
    #                [2017, 2017]]
    #
    #
    #    Q = Q2
    #    LR = LR2
    Q = int(eval(input()))
    LR = []
    for i in range(Q):
        LR.append(list(map(int, input().split())))
    # 1. find 2017-like number
    MAX_Q = 10**5
    like2017_list = judge_prime(MAX_Q)
    # judge
    csum = [0] * (MAX_Q + 1)
    i = 0
    cnt = 0
    for like2017 in like2017_list:
        while i < like2017:
            csum[i] = cnt
            i += 1
        cnt += 1
    for i in range(like2017_list[-1], MAX_Q + 1):
        csum[i] = cnt
    for i in range(Q):
        print((csum[LR[i][1]] - csum[LR[i][0] - 1]))


if __name__ == "__main__":
    main()

import sys

stdin = sys.stdin
sys.setrecursionlimit(10**5)


def li():
    return list(map(int, stdin.readline().split()))


def li_():
    return [int(x) - 1 for x in stdin.readline().split()]


def lf():
    return list(map(float, stdin.readline().split()))


def ls():
    return stdin.readline().split()


def ns():
    return stdin.readline().rstrip()


def lc():
    return list(ns())


def ni():
    return int(stdin.readline())


def nf():
    return float(stdin.readline())


from math import sqrt
from bisect import bisect_left, bisect_right

# 半開区間[lower, upper)の素数のリストを作成する
def make_prime_list(lower: int, upper: int) -> list:
    # 素数リストの初期化
    isPrime = [True] * upper
    primeList = []
    # 区間内の数字が0,1のみならここで終了
    if upper <= 2:
        return primeList
    # 区間内の数字に2以上のものがあるとき
    isPrime[0] = False
    isPrime[1] = False
    # エラトステネスの篩の処理
    for n in range(2, int(sqrt(upper)) + 2):
        if isPrime[n]:
            res = 2 * n
            while res < upper:
                isPrime[res] = False
                res += n
    # 区間内の素数を抽出
    for n in range(lower, upper):
        if isPrime[n]:
            primeList.append(n)
    return primeList


q = ni()
query = [tuple(li()) for _ in range(q)]
prime_list = set(make_prime_list(2, 10**5 + 1))
like2017 = []
for i in range(3, 10**5, 2):
    if (i in prime_list) and ((i + 1) // 2 in prime_list):
        like2017.append(i)
for l, r in query:
    print((bisect_right(like2017, r) - bisect_left(like2017, l)))

-import math as m +import sys + +stdin = sys.stdin +sys.setrecursionlimit(10**5) -def judge_prime(num): -    isPrime = [True] * (num + 1) +def li(): +    return list(map(int, stdin.readline().split())) + + +def li_(): +    return [int(x) - 1 for x in stdin.readline().split()] + + +def lf(): +    return list(map(float, stdin.readline().split())) + + +def ls(): +    return stdin.readline().split() + + +def ns(): +    return stdin.readline().rstrip() + + +def lc(): +    return list(ns()) + + +def ni(): +    return int(stdin.readline()) + + +def nf(): +    return float(stdin.readline()) + + +from math import sqrt +from bisect import bisect_left, bisect_right + +# 半開区間[lower, upper)の素数のリストを作成する +def make_prime_list(lower: int, upper: int) -> list: +    # 素数リストの初期化 +    isPrime = [True] * upper +    primeList = [] +    # 区間内の数字が0,1のみならここで終了 +    if upper <= 2: +        return primeList +    # 区間内の数字に2以上のものがあるとき -    border = m.sqrt(num) -    i = 2 -    while i <= border: -        if isPrime[i]: -            j = i * 2 -            while j <= num: -                isPrime[j] = False -                j += i -        i += 1 -    # prime_list = [] -    like2017_list = [] -    for prime in range(3, num + 1, 2): -        #        if isPrime[prime]: -        #            prime_list.append(prime) -        if isPrime[int(prime)] and isPrime[int((prime + 1) / 2)]: -            like2017_list.append(prime) -    return like2017_list +    # エラトステネスの篩の処理 +    for n in range(2, int(sqrt(upper)) + 2): +        if isPrime[n]: +            res = 2 * n +            while res < upper: +                isPrime[res] = False +                res += n +    # 区間内の素数を抽出 +    for n in range(lower, upper): +        if isPrime[n]: +            primeList.append(n) +    return primeList -def main(): -    # input -    #    Q1 = 1 -    #    LR1 = [[3,7]] -    # -    #    Q2 = 4 -    #    LR2 = [[13, 13], -    #                [7, 11], -    #                [7, 11], -    #                [2017, 2017]] -    # -    # -    #    Q = Q2 -    #    LR = LR2 -    Q = int(eval(input())) -    LR = [] -    for i in range(Q): -        LR.append(list(map(int, input().split()))) -    # 1. find 2017-like number -    MAX_Q = 10**5 -    like2017_list = judge_prime(MAX_Q) -    # judge -    csum = [0] * (MAX_Q + 1) -    i = 0 -    cnt = 0 -    for like2017 in like2017_list: -        while i < like2017: -            csum[i] = cnt -            i += 1 -        cnt += 1 -    for i in range(like2017_list[-1], MAX_Q + 1): -        csum[i] = cnt -    for i in range(Q): -        print((csum[LR[i][1]] - csum[LR[i][0] - 1])) - - -if __name__ == "__main__": -    main() +q = ni() +query = [tuple(li()) for _ in range(q)] +prime_list = set(make_prime_list(2, 10**5 + 1)) +like2017 = [] +for i in range(3, 10**5, 2): +    if (i in prime_list) and ((i + 1) // 2 in prime_list): +        like2017.append(i) +for l, r in query: +    print((bisect_right(like2017, r) - bisect_left(like2017, l)))