# 全てを先に計算しておき、累積和を使って結果を表示する。 今度コソ累積和

# それにより、同じ計算を何度もしなくてすむ。最大10^5になるはず。

# 



import math

from itertools import accumulate



def is_prime(n):

    if n == 1: return False



    for k in range(2, int(math.sqrt(n)) + 1):

        if n % k == 0:

            return False



    return True





# 2017に似た数



def is_like2017(n):

    if is_prime(n) and is_prime((n+1)//2):

        return True

    else:

        return False





Q = int(eval(input()))



l_list = [0]*Q

r_list = [0]*Q



for i in range(Q):

    l_list[i], r_list[i] = list(map(int, input().split()))

    

min_value = min(l_list)

max_value = max(r_list)



ans = []



for i in range(min_value, max_value+1):

    if i % 2 == 0:

        ans.append(0)

    elif is_prime(i) and is_like2017(i):

        ans.append(1)

    else:

        ans.append(0)



ans = [0] + list(accumulate(ans))        

        

for i in range(Q):

    print((ans[r_list[i]-min_value+1]-ans[l_list[i]-min_value]))

   


# ほんとうに全ての値を最初に計算し、累積和のリストを作成してしまおう。

# 計算時間は421msでOKだけど、答えが間違っている。＝＞なおした



import math



def is_prime(n):

    if n == 1: return False



    for k in range(2, int(math.sqrt(n)) + 1):

        if n % k == 0:

            return False



    return True





# 2017に似た数



def is_like2017(n):

    if is_prime(n) and is_prime((n+1)//2):

        return True

    else:

        return False





Q = int(eval(input()))



l_list = [0]*Q

r_list = [0]*Q



for i in range(Q):

    l_list[i], r_list[i] = list(map(int, input().split()))

    



ans = [0]



for i in range(1, 100000+1):

    if i % 2 == 0:

        ans.append(ans[i-1])

    elif is_like2017(i):

        ans.append(ans[i-1] + 1)

    else:

        ans.append(ans[i-1])    

        

for i in range(Q):

    print((ans[r_list[i]]-ans[l_list[i]-1]))

   
# 全てを先に計算しておき、累積和を使って結果を表示する。 今度コソ累積和
# それにより、同じ計算を何度もしなくてすむ。最大10^5になるはず。
#
import math
from itertools import accumulate


def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


# 2017に似た数
def is_like2017(n):
    if is_prime(n) and is_prime((n + 1) // 2):
        return True
    else:
        return False


Q = int(eval(input()))
l_list = [0] * Q
r_list = [0] * Q
for i in range(Q):
    l_list[i], r_list[i] = list(map(int, input().split()))
min_value = min(l_list)
max_value = max(r_list)
ans = []
for i in range(min_value, max_value + 1):
    if i % 2 == 0:
        ans.append(0)
    elif is_prime(i) and is_like2017(i):
        ans.append(1)
    else:
        ans.append(0)
ans = [0] + list(accumulate(ans))
for i in range(Q):
    print((ans[r_list[i] - min_value + 1] - ans[l_list[i] - min_value]))

# ほんとうに全ての値を最初に計算し、累積和のリストを作成してしまおう。
# 計算時間は421msでOKだけど、答えが間違っている。＝＞なおした
import math


def is_prime(n):
    if n == 1:
        return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True


# 2017に似た数
def is_like2017(n):
    if is_prime(n) and is_prime((n + 1) // 2):
        return True
    else:
        return False


Q = int(eval(input()))
l_list = [0] * Q
r_list = [0] * Q
for i in range(Q):
    l_list[i], r_list[i] = list(map(int, input().split()))
ans = [0]
for i in range(1, 100000 + 1):
    if i % 2 == 0:
        ans.append(ans[i - 1])
    elif is_like2017(i):
        ans.append(ans[i - 1] + 1)
    else:
        ans.append(ans[i - 1])
for i in range(Q):
    print((ans[r_list[i]] - ans[l_list[i] - 1]))

-# 全てを先に計算しておき、累積和を使って結果を表示する。 今度コソ累積和 -# それにより、同じ計算を何度もしなくてすむ。最大10^5になるはず。 -# +# ほんとうに全ての値を最初に計算し、累積和のリストを作成してしまおう。 +# 計算時間は421msでOKだけど、答えが間違っている。＝＞なおした -from itertools import accumulate -min_value = min(l_list) -max_value = max(r_list) -ans = [] -for i in range(min_value, max_value + 1): +ans = [0] +for i in range(1, 100000 + 1): -        ans.append(0) -    elif is_prime(i) and is_like2017(i): -        ans.append(1) +        ans.append(ans[i - 1]) +    elif is_like2017(i): +        ans.append(ans[i - 1] + 1) -        ans.append(0) -ans = [0] + list(accumulate(ans)) +        ans.append(ans[i - 1]) -    print((ans[r_list[i] - min_value + 1] - ans[l_list[i] - min_value])) +    print((ans[r_list[i]] - ans[l_list[i] - 1]))