import sys

import math

def input(): return sys.stdin.readline().rstrip()



def isPrime(n):

    m = (n + 1) // 2

    n_sqrt = int(math.sqrt(n))

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

        if n % i == 0 or m % i == 0:

            return 0

    else:

        return 1



def main():

    Q = int(eval(input()))



    MAX = 10 ** 5

    prime = [0] * MAX

    for i in range(3, MAX):

        prime[i] = prime[i-1] + isPrime(i)



    for _ in range(Q):

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

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

if __name__ == '__main__':

    main()
import sys

def input(): return sys.stdin.readline().rstrip()



def main():

    MAX = 10 ** 5

    Q = int(eval(input()))



    ans = [0] * (MAX + 1)

    sum = 0

    prime = set()

    memo = [False] * 2 + [True] * (MAX - 1)

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

        if memo[i]:

            prime.add(i)

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

                memo[j] = False

            if (i + 1) // 2 in prime:

                sum += 1

        ans[i] = sum

    

    for _ in range(Q):

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

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



if __name__ == '__main__':

    main()

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    else:
        return 1


def main():
    Q = int(eval(input()))
    MAX = 10**5
    prime = [0] * MAX
    for i in range(3, MAX):
        prime[i] = prime[i - 1] + isPrime(i)
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        print((prime[r] - prime[l - 1]))


if __name__ == "__main__":
    main()

import sys


def input():
    return sys.stdin.readline().rstrip()


def main():
    MAX = 10**5
    Q = int(eval(input()))
    ans = [0] * (MAX + 1)
    sum = 0
    prime = set()
    memo = [False] * 2 + [True] * (MAX - 1)
    for i in range(2, MAX + 1):
        if memo[i]:
            prime.add(i)
            for j in range(i * 2, MAX + 1, i):
                memo[j] = False
            if (i + 1) // 2 in prime:
                sum += 1
        ans[i] = sum
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        print((ans[r] - ans[l - 1]))


if __name__ == "__main__":
    main()

-import math -def isPrime(n): -    m = (n + 1) // 2 -    n_sqrt = int(math.sqrt(n)) -    for i in range(2, n_sqrt + 1): -        if n % i == 0 or m % i == 0: -            return 0 -    else: -        return 1 - - +    MAX = 10**5 -    MAX = 10**5 -    prime = [0] * MAX -    for i in range(3, MAX): -        prime[i] = prime[i - 1] + isPrime(i) +    ans = [0] * (MAX + 1) +    sum = 0 +    prime = set() +    memo = [False] * 2 + [True] * (MAX - 1) +    for i in range(2, MAX + 1): +        if memo[i]: +            prime.add(i) +            for j in range(i * 2, MAX + 1, i): +                memo[j] = False +            if (i + 1) // 2 in prime: +                sum += 1 +        ans[i] = sum -        print((prime[r] - prime[l - 1])) +        print((ans[r] - ans[l - 1]))