import math

import numpy as np



n = 10**5 + 1

p = [False] * n

c = [0] * n



def main():

    # 2からnまでの数字をsearch_listに入れる

    search_list = list(range(2,n))

    while True:

        # search_listの先頭の値が√nの値を超えたら処理終了

        if search_list[0] > math.sqrt(n):

            # search_listの残りの素数フラグを立てる

            for num in search_list:

                p[num] = True

            break

        else:

            # search_listの先頭の素数フラグを立てる

            tmp = search_list[0]

            p[tmp] = True

            # search_listの先頭をpopする

            search_list.pop(0)

            # search_listの先頭の倍数を取り除く

            search_list = [num for num in search_list if num % tmp != 0]



    # 1以上i以下のN-like数の数をc[i]とする

    for i in range(1,n):

        if p[i] and p[(i+1)//2]:

            c[i] = c[i-1] + 1

        else:

            c[i] = c[i-1]





    Q = int(eval(input()))

    for i in range(Q):

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

        print((c[r] - c[l-1]))

    



if __name__ == "__main__":

    main()

from math import ceil, sqrt

from itertools import accumulate

import sys

read = sys.stdin.read

readline = sys.stdin.readline

readlines = sys.stdin.readlines



def eratosthenes(n):

    p = []         # n以下の素数リスト

    t = [-1] * n   # t_iの素因数の内最小のもの

    t[0] = 0

    t[1] = 0



    for i in range(2, ceil(sqrt(n))):

        if t[i] == -1:

            p.append(i)

            #t[i] = i

            for j in range(2*i, n, i):

                if t[j] == -1:

                    t[j] = i

 

    for j in range(i+1, n):

        if t[j] == -1:

            p.append(j)

            #t[j] = j

 

    return p, t

 



def main():

    Q,*lr = list(map(int, read().split()))



    P, T = eratosthenes(10**5+5)

    table2017 = [0] * (10**5+5)

    for p in P:

        if T[(p+1)//2] == -1:

            table2017[p] = 1

    acc = list(accumulate(table2017))



    for l, r in zip(*[iter(lr)]*2):

        print((acc[r] - acc[l-1]))





if __name__ == "__main__":

    main()

import math
import numpy as np

n = 10**5 + 1
p = [False] * n
c = [0] * n


def main():
    # 2からnまでの数字をsearch_listに入れる
    search_list = list(range(2, n))
    while True:
        # search_listの先頭の値が√nの値を超えたら処理終了
        if search_list[0] > math.sqrt(n):
            # search_listの残りの素数フラグを立てる
            for num in search_list:
                p[num] = True
            break
        else:
            # search_listの先頭の素数フラグを立てる
            tmp = search_list[0]
            p[tmp] = True
            # search_listの先頭をpopする
            search_list.pop(0)
            # search_listの先頭の倍数を取り除く
            search_list = [num for num in search_list if num % tmp != 0]
    # 1以上i以下のN-like数の数をc[i]とする
    for i in range(1, n):
        if p[i] and p[(i + 1) // 2]:
            c[i] = c[i - 1] + 1
        else:
            c[i] = c[i - 1]
    Q = int(eval(input()))
    for i in range(Q):
        l, r = list(map(int, input().split()))
        print((c[r] - c[l - 1]))


if __name__ == "__main__":
    main()

from math import ceil, sqrt
from itertools import accumulate
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def eratosthenes(n):
    p = []  # n以下の素数リスト
    t = [-1] * n  # t_iの素因数の内最小のもの
    t[0] = 0
    t[1] = 0
    for i in range(2, ceil(sqrt(n))):
        if t[i] == -1:
            p.append(i)
            # t[i] = i
            for j in range(2 * i, n, i):
                if t[j] == -1:
                    t[j] = i
    for j in range(i + 1, n):
        if t[j] == -1:
            p.append(j)
            # t[j] = j
    return p, t


def main():
    Q, *lr = list(map(int, read().split()))
    P, T = eratosthenes(10**5 + 5)
    table2017 = [0] * (10**5 + 5)
    for p in P:
        if T[(p + 1) // 2] == -1:
            table2017[p] = 1
    acc = list(accumulate(table2017))
    for l, r in zip(*[iter(lr)] * 2):
        print((acc[r] - acc[l - 1]))


if __name__ == "__main__":
    main()

-import math -import numpy as np +from math import ceil, sqrt +from itertools import accumulate +import sys -n = 10**5 + 1 -p = [False] * n -c = [0] * n +read = sys.stdin.read +readline = sys.stdin.readline +readlines = sys.stdin.readlines + + +def eratosthenes(n): +    p = []  # n以下の素数リスト +    t = [-1] * n  # t_iの素因数の内最小のもの +    t[0] = 0 +    t[1] = 0 +    for i in range(2, ceil(sqrt(n))): +        if t[i] == -1: +            p.append(i) +            # t[i] = i +            for j in range(2 * i, n, i): +                if t[j] == -1: +                    t[j] = i +    for j in range(i + 1, n): +        if t[j] == -1: +            p.append(j) +            # t[j] = j +    return p, t -    # 2からnまでの数字をsearch_listに入れる -    search_list = list(range(2, n)) -    while True: -        # search_listの先頭の値が√nの値を超えたら処理終了 -        if search_list[0] > math.sqrt(n): -            # search_listの残りの素数フラグを立てる -            for num in search_list: -                p[num] = True -            break -        else: -            # search_listの先頭の素数フラグを立てる -            tmp = search_list[0] -            p[tmp] = True -            # search_listの先頭をpopする -            search_list.pop(0) -            # search_listの先頭の倍数を取り除く -            search_list = [num for num in search_list if num % tmp != 0] -    # 1以上i以下のN-like数の数をc[i]とする -    for i in range(1, n): -        if p[i] and p[(i + 1) // 2]: -            c[i] = c[i - 1] + 1 -        else: -            c[i] = c[i - 1] -    Q = int(eval(input())) -    for i in range(Q): -        l, r = list(map(int, input().split())) -        print((c[r] - c[l - 1])) +    Q, *lr = list(map(int, read().split())) +    P, T = eratosthenes(10**5 + 5) +    table2017 = [0] * (10**5 + 5) +    for p in P: +        if T[(p + 1) // 2] == -1: +            table2017[p] = 1 +    acc = list(accumulate(table2017)) +    for l, r in zip(*[iter(lr)] * 2): +        print((acc[r] - acc[l - 1]))