def isprime(n):

    '''check if integer n is a prime'''



    # make sure n is a positive integer

    n = abs(int(n))



    # 0 and 1 are not primes

    if n < 2:

        return False



    # 2 is the only even prime number

    if n == 2:

        return True



    # all other even numbers are not primes

    if not n & 1:

        return False



    # range starts with 3 and only needs to go up

    # the square root of n for all odd numbers

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

        if n % x == 0:

            return False



    return True



def resolve():

	q = int(eval(input()))

	qs = [list(map(int, input().split())) for _ in range(q)]

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

	for i in range(10**5):

		v = 1 if isprime(i+1) and isprime((i+2)/2) else 0

		t[i+1] = t[i] + v

	for l, r in qs:

		if l == r:

			print((1 if isprime(l) and isprime((l+2)/2) else 0))

		else:

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

resolve()
def sieve(n):

	is_prime = [1] * (n + 1)

	is_prime[0], is_prime[1] = 0, 0

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

		if not is_prime[i]:

			continue

		j = i*2

		while j <= n:

			is_prime[j] = 0

			j += i

	return is_prime



def resolve():

	q = int(eval(input()))

	qs = [list(map(int, input().split())) for _ in range(q)]

	ps = sieve(10**5)

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

	for i in range(len(ps)-1, 1, -1):

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

			continue

		ps[i] = 0

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

		seq[i+1] = seq[i] + ps[i+1]

	for l, r in qs:

		if l == r:

			print((ps[l]))

		else:

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

resolve()
def isprime(n):
    """check if integer n is a prime"""
    # make sure n is a positive integer
    n = abs(int(n))
    # 0 and 1 are not primes
    if n < 2:
        return False
    # 2 is the only even prime number
    if n == 2:
        return True
    # all other even numbers are not primes
    if not n & 1:
        return False
    # range starts with 3 and only needs to go up
    # the square root of n for all odd numbers
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True


def resolve():
    q = int(eval(input()))
    qs = [list(map(int, input().split())) for _ in range(q)]
    t = [0] * (10**5 + 1)
    for i in range(10**5):
        v = 1 if isprime(i + 1) and isprime((i + 2) / 2) else 0
        t[i + 1] = t[i] + v
    for l, r in qs:
        if l == r:
            print((1 if isprime(l) and isprime((l + 2) / 2) else 0))
        else:
            print((t[r] - t[l - 1]))


resolve()

def sieve(n):
    is_prime = [1] * (n + 1)
    is_prime[0], is_prime[1] = 0, 0
    for i in range(2, n + 1):
        if not is_prime[i]:
            continue
        j = i * 2
        while j <= n:
            is_prime[j] = 0
            j += i
    return is_prime


def resolve():
    q = int(eval(input()))
    qs = [list(map(int, input().split())) for _ in range(q)]
    ps = sieve(10**5)
    seq = [0] * (10**5 + 1)
    for i in range(len(ps) - 1, 1, -1):
        if ps[i] and ps[(i + 1) // 2]:
            continue
        ps[i] = 0
    for i in range(1, 10**5):
        seq[i + 1] = seq[i] + ps[i + 1]
    for l, r in qs:
        if l == r:
            print((ps[l]))
        else:
            print((seq[r] - seq[l - 1]))


resolve()

-def isprime(n): -    """check if integer n is a prime""" -    # make sure n is a positive integer -    n = abs(int(n)) -    # 0 and 1 are not primes -    if n < 2: -        return False -    # 2 is the only even prime number -    if n == 2: -        return True -    # all other even numbers are not primes -    if not n & 1: -        return False -    # range starts with 3 and only needs to go up -    # the square root of n for all odd numbers -    for x in range(3, int(n**0.5) + 1, 2): -        if n % x == 0: -            return False -    return True +def sieve(n): +    is_prime = [1] * (n + 1) +    is_prime[0], is_prime[1] = 0, 0 +    for i in range(2, n + 1): +        if not is_prime[i]: +            continue +        j = i * 2 +        while j <= n: +            is_prime[j] = 0 +            j += i +    return is_prime -    t = [0] * (10**5 + 1) -    for i in range(10**5): -        v = 1 if isprime(i + 1) and isprime((i + 2) / 2) else 0 -        t[i + 1] = t[i] + v +    ps = sieve(10**5) +    seq = [0] * (10**5 + 1) +    for i in range(len(ps) - 1, 1, -1): +        if ps[i] and ps[(i + 1) // 2]: +            continue +        ps[i] = 0 +    for i in range(1, 10**5): +        seq[i + 1] = seq[i] + ps[i + 1] -            print((1 if isprime(l) and isprime((l + 2) / 2) else 0)) +            print((ps[l])) -            print((t[r] - t[l - 1])) +            print((seq[r] - seq[l - 1]))