"""

事前に、100000以下の数のうち、2017に似た数を列挙しておく。

メモの仕方としては、2017に似た数を小さい順に並べておけばよい。

2017に似た数を探すのは、まず100000以下の素数を全部列挙して、その中で条件に当てはまるものを愚直に探す。

"""

memo = [1]*(100001)

memo[0] = 0

memo[1] = 0

primes = set()

for i in range(100001):

    if memo[i] == 1:

        primes.add(i)

        for j in range(i*2,100001,i):

            memo[j] = 0



answers = []

for p in primes:

    if (p+1)//2 in primes:

        answers.append(p)



Q = int(eval(input()))

for _ in range(Q):

    ans = 0

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

    for a in answers:

        if l<=a<=r:

            ans += 1

    print(ans)
"""

10^5以下の素数を列挙しておく。

それをもとに、10^5以下の各整数以下の2017に似た数の個数のメモを作成する。

"""

#10^5以下の素数を列挙

prime = [1] * (100001)

prime[0] = 0

prime[1] = 0

for i in range(2,100001):

    if prime[i]:

        for j in range(i*i,100001,i):

            prime[j] = 0



memo = [0]*(100001)

for i in range(3,100001):

    memo[i] = memo[i-1]

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

        memo[i] += 1



Q = int(eval(input()))

for _ in range(Q):

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

    print((memo[r]-memo[l-1]))
"""
事前に、100000以下の数のうち、2017に似た数を列挙しておく。
メモの仕方としては、2017に似た数を小さい順に並べておけばよい。
2017に似た数を探すのは、まず100000以下の素数を全部列挙して、その中で条件に当てはまるものを愚直に探す。
"""
memo = [1] * (100001)
memo[0] = 0
memo[1] = 0
primes = set()
for i in range(100001):
    if memo[i] == 1:
        primes.add(i)
        for j in range(i * 2, 100001, i):
            memo[j] = 0
answers = []
for p in primes:
    if (p + 1) // 2 in primes:
        answers.append(p)
Q = int(eval(input()))
for _ in range(Q):
    ans = 0
    l, r = list(map(int, input().split()))
    for a in answers:
        if l <= a <= r:
            ans += 1
    print(ans)

"""
10^5以下の素数を列挙しておく。
それをもとに、10^5以下の各整数以下の2017に似た数の個数のメモを作成する。
"""
# 10^5以下の素数を列挙
prime = [1] * (100001)
prime[0] = 0
prime[1] = 0
for i in range(2, 100001):
    if prime[i]:
        for j in range(i * i, 100001, i):
            prime[j] = 0
memo = [0] * (100001)
for i in range(3, 100001):
    memo[i] = memo[i - 1]
    if prime[i] and prime[(i + 1) // 2]:
        memo[i] += 1
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((memo[r] - memo[l - 1]))

-事前に、100000以下の数のうち、2017に似た数を列挙しておく。 -メモの仕方としては、2017に似た数を小さい順に並べておけばよい。 -2017に似た数を探すのは、まず100000以下の素数を全部列挙して、その中で条件に当てはまるものを愚直に探す。 +10^5以下の素数を列挙しておく。 +それをもとに、10^5以下の各整数以下の2017に似た数の個数のメモを作成する。 -memo = [1] * (100001) -memo[0] = 0 -memo[1] = 0 -primes = set() -for i in range(100001): -    if memo[i] == 1: -        primes.add(i) -        for j in range(i * 2, 100001, i): -            memo[j] = 0 -answers = [] -for p in primes: -    if (p + 1) // 2 in primes: -        answers.append(p) +# 10^5以下の素数を列挙 +prime = [1] * (100001) +prime[0] = 0 +prime[1] = 0 +for i in range(2, 100001): +    if prime[i]: +        for j in range(i * i, 100001, i): +            prime[j] = 0 +memo = [0] * (100001) +for i in range(3, 100001): +    memo[i] = memo[i - 1] +    if prime[i] and prime[(i + 1) // 2]: +        memo[i] += 1 -    ans = 0 -    for a in answers: -        if l <= a <= r: -            ans += 1 -    print(ans) +    print((memo[r] - memo[l - 1]))