from itertools import accumulate

def prm(x):

    if x == 1 or x == 4:

        return False

    for i in range(2,int(x**0.5+1)):

        if x%i==0:

            return False

    else:

        return True

def like2017(x):

    if x == 2:

        return False

    if prm(x) and prm((x+1)//2):

        return True

q=int(eval(input()))

l=[0]*(10**5+1)

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

    if like2017(i):

        l[i]=1

acl = list(accumulate(l))

for i in range(q):

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

    print((acl[r]-acl[l-1]))
from itertools import accumulate

import sys

input=sys.stdin.readline

def prm(x):

    if x == 1 or x == 4:

        return False

    for i in range(2,int(x**0.5+1)):

        if x%i==0:

            return False

    else:

        return True

def like2017(x):

    if x == 2:

        return False

    if prm(x) and prm((x+1)//2):

        return True

q=int(eval(input()))

l=[0]*(10**5+1)

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

    if like2017(i):

        l[i]=1

acl = list(accumulate(l))

for i in range(q):

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

    print((acl[r]-acl[l-1]))
from itertools import accumulate


def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2, int(x**0.5 + 1)):
        if x % i == 0:
            return False
    else:
        return True


def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x + 1) // 2):
        return True


q = int(eval(input()))
l = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    if like2017(i):
        l[i] = 1
acl = list(accumulate(l))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((acl[r] - acl[l - 1]))

from itertools import accumulate
import sys

input = sys.stdin.readline


def prm(x):
    if x == 1 or x == 4:
        return False
    for i in range(2, int(x**0.5 + 1)):
        if x % i == 0:
            return False
    else:
        return True


def like2017(x):
    if x == 2:
        return False
    if prm(x) and prm((x + 1) // 2):
        return True


q = int(eval(input()))
l = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    if like2017(i):
        l[i] = 1
acl = list(accumulate(l))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((acl[r] - acl[l - 1]))

+import sys + +input = sys.stdin.readline