def is_prime(q):

    if q == 2: return True

    if q < 2 or q&1 == 0: return False

    return pow(5, q-1, q)*pow(7, q-1, q) == 1

    

s = [561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831]

b = [5,7]

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

  if i in s:

    continue

  if is_prime(i):

    b.append(i)



a = set([2*i-1 for i in b])

b = set(b)

chk = sorted(list(a&b))

 

from bisect import bisect,bisect_left

import sys

input = sys.stdin.readline

 

q = int(eval(input()))

for i in range(q):

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

  print((bisect(chk,r)-bisect_left(chk,l)))
def is_prime(q):

    if q == 2: return True

    if q < 2 or q&1 == 0: return False

    return pow(5, q-1, q)*pow(7, q-1, q) == 1

  

def main():

  s = set([561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831])

  b = [5,7]

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

    if i in s:

      continue

    if is_prime(i):

      b.append(i)



  a = set([2*i-1 for i in b])

  b = set(b)

  chk = sorted(tuple(a&b))



  from bisect import bisect,bisect_left

  import sys

  input = sys.stdin.readline



  q = int(eval(input()))

  for i in range(q):

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

    print((bisect(chk,r)-bisect_left(chk,l)))

    

if __name__ == '__main__':

    main()
def is_prime(q):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(5, q - 1, q) * pow(7, q - 1, q) == 1


s = [561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831]
b = [5, 7]
for i in range(2, 10**5):
    if i in s:
        continue
    if is_prime(i):
        b.append(i)
a = set([2 * i - 1 for i in b])
b = set(b)
chk = sorted(list(a & b))
from bisect import bisect, bisect_left
import sys

input = sys.stdin.readline
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((bisect(chk, r) - bisect_left(chk, l)))

def is_prime(q):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(5, q - 1, q) * pow(7, q - 1, q) == 1


def main():
    s = set([561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831])
    b = [5, 7]
    for i in range(2, 10**5):
        if i in s:
            continue
        if is_prime(i):
            b.append(i)
    a = set([2 * i - 1 for i in b])
    b = set(b)
    chk = sorted(tuple(a & b))
    from bisect import bisect, bisect_left
    import sys

    input = sys.stdin.readline
    q = int(eval(input()))
    for i in range(q):
        l, r = list(map(int, input().split()))
        print((bisect(chk, r) - bisect_left(chk, l)))


if __name__ == "__main__":
    main()

-s = [561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831] -b = [5, 7] -for i in range(2, 10**5): -    if i in s: -        continue -    if is_prime(i): -        b.append(i) -a = set([2 * i - 1 for i in b]) -b = set(b) -chk = sorted(list(a & b)) -from bisect import bisect, bisect_left -import sys +def main(): +    s = set([561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831]) +    b = [5, 7] +    for i in range(2, 10**5): +        if i in s: +            continue +        if is_prime(i): +            b.append(i) +    a = set([2 * i - 1 for i in b]) +    b = set(b) +    chk = sorted(tuple(a & b)) +    from bisect import bisect, bisect_left +    import sys -input = sys.stdin.readline -q = int(eval(input())) -for i in range(q): -    l, r = list(map(int, input().split())) -    print((bisect(chk, r) - bisect_left(chk, l))) +    input = sys.stdin.readline +    q = int(eval(input())) +    for i in range(q): +        l, r = list(map(int, input().split())) +        print((bisect(chk, r) - bisect_left(chk, l))) + + +if __name__ == "__main__": +    main()