# -*- coding: utf-8 -*-

import sys

import random



def main():

	Q = int(eval(input()))

	maps = []

	r_max = 0

	for _ in range(Q):

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

		maps.append((l, r))

		if r_max < r:

			r_max = r

			

	#marix = getPrimeNumList(r_max)

				

	base = [0] * (r_max+1)

	counts = 0

	for i in range(r_max+1):

		if i == 0 or i == 1:

			continue

		if (i+1) % 2 == 0 and is_prime(i) == True:

			tmp = (i+1) / 2

			if is_prime(tmp) == True:

				counts += 1

		base[i] = counts

			

	

	for i in maps:

		l, r = i

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

			

		

def getPrimeNumList(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]]

	

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 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 random


def main():
    Q = int(eval(input()))
    maps = []
    r_max = 0
    for _ in range(Q):
        l, r = list(map(int, input().split(" ")))
        maps.append((l, r))
        if r_max < r:
            r_max = r
    # marix = getPrimeNumList(r_max)
    base = [0] * (r_max + 1)
    counts = 0
    for i in range(r_max + 1):
        if i == 0 or i == 1:
            continue
        if (i + 1) % 2 == 0 and is_prime(i) == True:
            tmp = (i + 1) / 2
            if is_prime(tmp) == True:
                counts += 1
        base[i] = counts
    for i in maps:
        l, r = i
        print((base[r] - base[l - 1]))


def getPrimeNumList(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]]


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

-import random +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 -    maps = [] -    r_max = 0 -    for _ in range(Q): -        l, r = list(map(int, input().split(" "))) -        maps.append((l, r)) -        if r_max < r: -            r_max = r -    # marix = getPrimeNumList(r_max) -    base = [0] * (r_max + 1) -    counts = 0 -    for i in range(r_max + 1): -        if i == 0 or i == 1: +    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) -        if (i + 1) % 2 == 0 and is_prime(i) == True: -            tmp = (i + 1) / 2 -            if is_prime(tmp) == True: -                counts += 1 -        base[i] = counts -    for i in maps: +        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: -        print((base[r] - base[l - 1])) - - -def getPrimeNumList(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]] +        print((mapd[r] - mapd[l - 1]))