def get_sieve_of_eratosthenes(n):

    if not isinstance(n, int):

        raise TypeError('n is int type.')

    if n < 2:

        raise ValueError('n is more than 2')

    prime = [2]

    limit = int(n**0.5)

    data = [i + 1 for i in range(2, n, 2)]

    while True:

        p = data[0]

        if limit <= p:

            return prime + data

        prime.append(p)

        data = [e for e in data if e % p != 0]





q = int(eval(input()))

lrl = []

for _ in range(q):

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



primes = set(get_sieve_of_eratosthenes(10**5))

like2017s = []

cnt_dict = {}

cnt_dict[-1] = 0

for i in range(10**5//2):

    num = i*2+1

    num2 = (num+1)//2

    if num in primes and num2 in primes:

        cnt_dict[num] = cnt_dict[num-2]+1

    else:

        cnt_dict[num] = cnt_dict[num-2]



for lr in lrl:

    l,r = lr

    print((cnt_dict[r]-cnt_dict[l-2]))
def primes(n):

    is_prime = [True] * (n + 1)

    is_prime[0] = False

    is_prime[1] = False

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

        if not is_prime[i]:

            continue

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

            is_prime[j] = False

    return [i for i in range(n + 1) if is_prime[i]]



sums = [0,0,0]

curr_sum = 0

ps = primes(10**3)

pset = set(ps)

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

    for p in ps:

        if i%p == 0 and i not in pset:

            break

        if ((i+1)//2)%p == 0 and ((i+1)//2) not in pset:

            break

    else:

        curr_sum += 1

        # print(i)

    sums.append(curr_sum)

    



q = int(eval(input()))

ansl = []

for _ in range(q):

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

    ans = sums[r] - sums[l-1]

    ansl.append(ans)



for a in ansl: print(a)



# print(sums[:54])

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int type.")
    if n < 2:
        raise ValueError("n is more than 2")
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


q = int(eval(input()))
lrl = []
for _ in range(q):
    lrl.append(list(map(int, input().split())))
primes = set(get_sieve_of_eratosthenes(10**5))
like2017s = []
cnt_dict = {}
cnt_dict[-1] = 0
for i in range(10**5 // 2):
    num = i * 2 + 1
    num2 = (num + 1) // 2
    if num in primes and num2 in primes:
        cnt_dict[num] = cnt_dict[num - 2] + 1
    else:
        cnt_dict[num] = cnt_dict[num - 2]
for lr in lrl:
    l, r = lr
    print((cnt_dict[r] - cnt_dict[l - 2]))

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


sums = [0, 0, 0]
curr_sum = 0
ps = primes(10**3)
pset = set(ps)
for i in range(3, 10**5 + 1):
    for p in ps:
        if i % p == 0 and i not in pset:
            break
        if ((i + 1) // 2) % p == 0 and ((i + 1) // 2) not in pset:
            break
    else:
        curr_sum += 1
        # print(i)
    sums.append(curr_sum)
q = int(eval(input()))
ansl = []
for _ in range(q):
    l, r = list(map(int, input().split()))
    ans = sums[r] - sums[l - 1]
    ansl.append(ans)
for a in ansl:
    print(a)
# print(sums[:54])

-def get_sieve_of_eratosthenes(n): -    if not isinstance(n, int): -        raise TypeError("n is int type.") -    if n < 2: -        raise ValueError("n is more than 2") -    prime = [2] -    limit = int(n**0.5) -    data = [i + 1 for i in range(2, n, 2)] -    while True: -        p = data[0] -        if limit <= p: -            return prime + data -        prime.append(p) -        data = [e for e in data if e % p != 0] +def primes(n): +    is_prime = [True] * (n + 1) +    is_prime[0] = False +    is_prime[1] = False +    for i in range(2, int(n**0.5) + 1): +        if not is_prime[i]: +            continue +        for j in range(i * 2, n + 1, i): +            is_prime[j] = False +    return [i for i in range(n + 1) if is_prime[i]] +sums = [0, 0, 0] +curr_sum = 0 +ps = primes(10**3) +pset = set(ps) +for i in range(3, 10**5 + 1): +    for p in ps: +        if i % p == 0 and i not in pset: +            break +        if ((i + 1) // 2) % p == 0 and ((i + 1) // 2) not in pset: +            break +    else: +        curr_sum += 1 +        # print(i) +    sums.append(curr_sum) -lrl = [] +ansl = [] -    lrl.append(list(map(int, input().split()))) -primes = set(get_sieve_of_eratosthenes(10**5)) -like2017s = [] -cnt_dict = {} -cnt_dict[-1] = 0 -for i in range(10**5 // 2): -    num = i * 2 + 1 -    num2 = (num + 1) // 2 -    if num in primes and num2 in primes: -        cnt_dict[num] = cnt_dict[num - 2] + 1 -    else: -        cnt_dict[num] = cnt_dict[num - 2] -for lr in lrl: -    l, r = lr -    print((cnt_dict[r] - cnt_dict[l - 2])) +    l, r = list(map(int, input().split())) +    ans = sums[r] - sums[l - 1] +    ansl.append(ans) +for a in ansl: +    print(a) +# print(sums[:54])