CodeEff/ECCO huggingface dataset:
# Original solution
# TLEするっぽいなー
Q = int(eval(input()))
LR = [tuple(map(int,input().split())) for _ in range(Q)]

N = 100010
# まずは素数列挙
P = []
A = [True]*N
for i in range(2,N):
    if A[i]:
        P.append(i)
        j = 2
        while i*j < N:
            A[i*j] = False
            j += 1

# 整数iまでの「2017数」を数える
Ans = [0]*N
for p in P:
    if p==2:
        continue
    if (p+1)//2 in P:
        Ans[p] = 1

for i in range(1,N):
    Ans[i] += Ans[i-1]

for (l,r) in LR:
    print((Ans[r] - Ans[l-1]))

# Optimized solution
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
N = 100010
primes = []
is_prime = [True]*N
for i in range(2,N):
    if is_prime[i]:
        primes.append(i)
        j = 2
        while i*j < N:
            is_prime[i*j] = False
            j += 1


# -------------------------------------------------------------
# main
# -------------------------------------------------------------

Q = int(eval(input()))
LR = [tuple(map(int,input().split())) for _ in range(Q)]

# 2017数の判定リストを作る
Ans = [0]*N
for p in primes:
    if p==2:
        continue
    # pは素数であるので、(p+1)//2が素数であれば 2017数
    if (p+1)//2 in primes:
        Ans[p] = 1

# 範囲計算なので累積和
for i in range(1,N):
    Ans[i] += Ans[i-1]

# クエリを処理
for l,r in LR:
    print((Ans[r] - Ans[l-1]))
# Original solution
from math import ceil, sqrt

Q = int(eval(input()))
querys = [tuple(map(int, input().split())) for i in range(Q)]

N = max(list(map(max, querys)))

Primes = [False] * 2 + [True] * (N - 1)
for i in range(3, N + 1):
    for j in range(2, ceil(sqrt(i)) + 1):
        if i % j == 0:
            Primes[i] = False

s2017s = [False] * (N + 1)
for i in range(1, N + 1, 2):
    if Primes[i] and Primes[(i + 1) // 2]:
        s2017s[i] = True

nums = [0] * (N + 1)
for i in range(1, N + 1, 2):
    nums[i] = nums[i - 2]
    if s2017s[i]:
        nums[i] += 1

for li, ri in querys:
    print((nums[ri] - nums[max(0, li - 2)]))


# Optimized solution
from math import ceil, sqrt

Q = int(eval(input()))
querys = [tuple(map(int, input().split())) for i in range(Q)]

N = max(list(map(max, querys)))

Primes = [False] * 2 + [True] * (N - 1)
for i in range(3, N + 1):
    for j in range(2, ceil(sqrt(i)) + 1):
        if i % j == 0:
            Primes[i] = False
            break

s2017s = [False] * (N + 1)
for i in range(1, N + 1, 2):
    if Primes[i] and Primes[(i + 1) // 2]:
        s2017s[i] = True

nums = [0] * (N + 1)
for i in range(1, N + 1, 2):
    nums[i] = nums[i - 2]
    if s2017s[i]:
        nums[i] += 1

for li, ri in querys:
    print((nums[ri] - nums[max(0, li - 2)]))
# Original solution
import math
import sys

prime_numbers = set()
input = lambda: sys.stdin.readline().strip()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def query(l, r):
    count = 0
    for x in range(l, r + 1, 2):
        if is_primenumber(x) and is_primenumber((x + 1) // 2):
            count += 1
    print(count)


if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1):
        is_primenumber(i)
    Q = int(eval(input()))

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        query(l, r)


# Optimized solution
import math
import itertools
import sys

prime_numbers = set()
table = [0 for i in range(10 ** 5 + 1)]
input = lambda: sys.stdin.readline().strip()


def is_primenumber(x):
    if x in prime_numbers:
        return True
    if x == 1:
        return False
    elif x == 2:
        prime_numbers.add(2)
        return True
    else:
        for i in range(2, int(math.sqrt(x)) + 1):
            if x % i == 0:
                return False
        prime_numbers.add(x)
        return True


def is_like_2017(x):
    return is_primenumber(x) and is_primenumber((x + 1) // 2)


def query(l, r):
    print((table[r] - table[l - 1]))


if __name__ == "__main__":
    for i in range(1, 10 ** 5 + 1, 2):
        if is_like_2017(i):
            table[i] += 1
    table = [x for x in itertools.accumulate(table)]
    Q = int(eval(input()))

    for _ in range(Q):
        l, r = [int(x) for x in input().split(" ")]
        query(l, r)
# Original solution
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


q = int(eval(input()))
scope = [tuple(map(int, input().split())) for _ in range(q)]
prime_cnt = [0] * (10 ** 5 + 1)
for i in range(1, 10 ** 5 + 1):
    prime_cnt[i] = prime_cnt[i - 1]
    if ((i + 1) / 2) % 1 == 0 and is_prime(i) and is_prime((i + 1) / 2):
        prime_cnt[i] += 1

for i in range(q):
    left = scope[i][0]
    right = scope[i][1]
    print((prime_cnt[right] - prime_cnt[left - 1]))

# Optimized solution
import math
q = int(eval(input()))
scope = [tuple(map(int, input().split())) for _ in range(q)]
prime_flag = [True] * (10 ** 5 + 1)
prime_flag[0] = False
prime_flag[1] = False
prime_cnt = [0] * (10 ** 5 + 1)

for i in range(2, math.ceil(math.sqrt(10 ** 5))):
    for j in range(i + i, 10 ** 5 + 1, i):
        prime_flag[j] = False


for i in range(2, 10 ** 5 + 1):
    prime_cnt[i] = prime_cnt[i - 1]
    num = (i + 1) / 2
    if num % 1 == 0 and prime_flag[i] and prime_flag[int(num)]:
        prime_cnt[i] += 1

for i in range(q):
    left = scope[i][0]
    right = scope[i][1]
    print((prime_cnt[right] - prime_cnt[left - 1]))
# Original solution
from itertools import accumulate
N = 100000
prime = [True for _ in range(N+1)]
prime[0] = False
prime[1] = False
i = 2
for i in range(N+1):
    if prime[i]:
        for j in range(2*i, N+1, i):
            prime[j] = False
prime2 = [0 for _ in range(N+1)]
for i in range(N+1):
    if prime[i] and prime[(i+1)//2]:
        prime2[i] = 1
acc = list(accumulate(prime2))

Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((acc[r] - acc[l-1]))


# Optimized solution
from itertools import accumulate
N = 100000
prime = [True for _ in range(N+1)]
prime[0] = False
prime[1] = False
i = 2
for i in range(N+1):
    if prime[i]:
        for j in range(2*i, N+1, i):
            prime[j] = False

prime2 = [1 if prime[i] and prime[(i+1)//2] else 0 for i in range(N+1)]
acc = list(accumulate(prime2))

Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((acc[r] - acc[l-1]))
# Original solution
prime=[]
n=10**5
is_prime=True
for i in range(2,n+1):
    is_prime=True
    for p in prime:
        if i%p==0:
            is_prime=False
            break
    if is_prime:
        prime.append(i)
q=int(eval(input()))
query=[[int(i) for i in input().split()] for j in range(q)]
for qu in query:
    cnt=0
    for j in range(qu[0], qu[1]+1, 2):
        if (j in prime) and (((j+1)//2) in prime):
            cnt+=1
    print(cnt)        


# Optimized solution
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

num = 10**5+10
Q = int(eval(input()))
prime_numbers = primes(num)
prime_set = set(prime_numbers)
prime_count = [0]*(num+1)
for pi in prime_numbers:
    if (pi+1)//2 in prime_set:
        prime_count[pi]+=1
for i in range(num):
    prime_count[i+1]+=prime_count[i]
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((prime_count[r]-prime_count[l-1]))
# Original solution
from math import sqrt
q = int(eval(input()))

primes = {i for i in range(2,10**5 + 1)}
for i in range(2,int(sqrt(10**5+1)) + 1):
    if i in primes:
        mul = 2
        while i*mul <= 10**5:
            primes.discard(i*mul)
            mul += 1

ret = [0]*(1 + 10**5)
for i in range(3,1 + 10**5):
    if i&1:
        if i in primes and (i+1)/2 in primes:
            ret[i] = ret[i-1] + 1
        else:
            ret[i] = ret[i-1]
    else:
        ret[i] = ret[i-1]

for i in range(q):
    l, r = (int(i) for i in input().split())
    print((ret[r] - ret[l-1]))

# Optimized solution
def main():
    from itertools import accumulate

    def Eratosthenes(x: int) -> set:
        from math import sqrt
        sup = int(x)
        primes = {i for i in range(2, sup+1)}
        for i in range(2, int(sqrt(sup+1))+1):
            if i in primes:
                mul = 2
                while i*mul <= sup:
                    primes.discard(i*mul)
                    mul += 1
        return primes
    P = Eratosthenes(10**5+5)
    A = [0]*(10**5+5)
    for i in range(3, 10**5+5):
        if i in P and (i+1)//2 in P:
            A[i] += 1
    S = list(accumulate(A))

    Q = int(eval(input()))
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    for le, ri in LR:
        print((S[ri] - S[le-1]))


if __name__ == '__main__':
    main()
# Original solution
def main():
    Q = int(eval(input()))

    def Eratosthenes(sup: int) -> set:
        primes = [True for i in range(sup+1)]
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if sup < i*i:
                break
            if primes[i]:
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    mul += 1
        return {i for i in range(sup+1) if primes[i]}
    primes = Eratosthenes(10**5)
    S = [0]*(10**5+1)
    for a in range(2, 10**5+1):
        if a in primes and (a+1)//2 in primes:
            S[a] = 1
        S[a] += S[a-1]

    for _ in range(Q):
        le, ri = (int(i) for i in input().split())
        print((S[ri] - S[le-1]))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    import sys
    input = sys.stdin.buffer.readline
    Q = int(eval(input()))

    def Eratosthenes(sup: int) -> set:
        primes = [True for i in range(sup+1)]
        primes[0] = False
        primes[1] = False
        for i in range(2, sup+1):
            if sup < i*i:
                break
            if primes[i]:
                mul = 2
                while i*mul <= sup:
                    primes[i*mul] = False
                    mul += 1
        return {i for i in range(sup+1) if primes[i]}
    primes = Eratosthenes(10**5)
    S = [0]*(10**5+1)
    for a in range(2, 10**5+1):
        if a in primes and (a+1)//2 in primes:
            S[a] = 1
        S[a] += S[a-1]

    for _ in range(Q):
        le, ri = (int(i) for i in input().split())
        print((S[ri] - S[le-1]))


if __name__ == '__main__':
    main()
# Original solution
def main():
    q=int(eval(input()))
    aa=0
    bb=0
    a=[]
    b=[]
    ac=[]
    bc=[]
    for _ in range(q):
        aa,bb=list(map(int,input().split()))
        a.append(aa)
        b.append(bb)
        # ac.append(aa)
        # bc.append(bb)

    # sorted(a)
    # sorted(b)
    bm=max(b)
    ans=[0]*100001
    flg=[0]*100001
    flg[0]=1
    flg[1]=1
    ans[2]=1
    ii=int((bm+1)**0.5)
    for i in range(2,100001):

        if flg[i]==0:
            flg[i]=1
            ans[i]=1
            for j in range(i,int(100001**0.5),i):
                flg[j]=1
    for i in range(0,q):
        cnt=0
        for j in range(a[i],b[i]+1):
            if ans[j]==1 and ans[(j+1)//2]==1:
                cnt+=1
        print(cnt)
    # print(ans[:8])
if __name__=='__main__':
    main()


# Optimized solution
def main():
    q=int(eval(input()))
    aa=0
    bb=0
    a=[]
    b=[]
    ac=[]
    bc=[]
    for _ in range(q):
        aa,bb=list(map(int,input().split()))
        a.append(aa)
        b.append(bb)
        # ac.append(aa)
        # bc.append(bb)

    # sorted(a)
    # sorted(b)
    bm=max(b)
    ans=[0]*100001
    flg=[0]*100001
    flg[0]=1
    flg[1]=1
    ans[2]=1
    ii=int((bm+1)**0.5)
    for i in range(2,100001):

        if flg[i]==0:
            flg[i]=1
            ans[i]=1
            for j in range(i,100001,i):
                flg[j]=1
    ans2=[]
    cnt=0
    for i in range(0,100001):
        if ans[i]==1 and ans[(i+1)//2]==1:
            cnt+=1
        ans2.append(cnt)
    # print(ans[:11])
    # print(ans2[:11])
    for i in range(0,q):
        print((ans2[b[i]]-ans2[a[i]-1]))
    # print(ans[:8])
if __name__=='__main__':
    main()
# Original solution
import math
from itertools import accumulate


def is_prime(n):
    if n == 1:
        return 0

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

    return 1


Q = int(eval(input()))
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

min_L = min(L)
max_R = max(R)

check = []
for i in range(min_L, max_R+1):
    if (i % 2 == 1):
        flg = (is_prime(i) and is_prime((i+1)/2))
    else:
        flg = 0
    check.append(flg)

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print((check[R[i] - min_L + 1] - check[L[i] - min_L]))


# Optimized solution
from itertools import accumulate


# エラトステネスの篩（素数）
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return [False] + is_prime, table


Q = int(eval(input()))
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

max_R = max(R)
is_prime, table = sieve(max_R)

check = [0]*(max_R + 1)
for i in range(0, max_R + 1):
    if (i % 2 == 1):
        if (is_prime[i] and is_prime[(i+1)//2]):
            check[i] = 1

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print((check[R[i] + 1] - check[L[i]]))
# Original solution
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
Q = int(eval(input()))
ans = [0] * (10**5+1)
prime = [0] * (10**5+1)
for i in range(1,10**5+1):
    if is_prime(i):
        prime[i] = 1
        if prime[(i+1)//2] == 1:
            ans[i] = ans[i-1] + 1
            continue
    ans[i] = ans[i-1]
disp_ans = 0
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((ans[r]-ans[l-1]))

# Optimized solution
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return is_prime
Q = int(eval(input()))
ans = [0] * (10**5+1)
prime = primes(10**5)
for i in range(1,10**5+1):
    if prime[i] == 1 and prime[(i+1)//2] == 1:
        ans[i] = ans[i-1] + 1
        continue
    ans[i] = ans[i-1]
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((ans[r]-ans[l-1]))
# Original solution
import sys


def solve(l, r, primeset):
    res = 0
    for i in range(l, r + 1, 2):
        if i in primeset and (i + 1) // 2 in primeset:
            res += 1
    return res


input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    primelist = [2]
    A = 10 ** 5 + 10
    for L in range(3, A, 2):
        if all(L % L2 != 0 for L2 in primelist):
            primelist.append(L)
    primeset = set(primelist)
    # print(primelist[:20])
    Q = int(eval(input()))
    for i in range(Q):
        l, r = list(map(int, input().split()))
        print((solve(l, r, primeset)))


if __name__ == "__main__":
    main()


# Optimized solution
MAX = 10 ** 5 + 1
f = [True] * (MAX)
c = [0] * (MAX + 1)
for i in range(2, MAX):
    if f[i]:
        for j in range(i + i, MAX, i):
            f[j] = False
for i in range(3, MAX, 2):
    if f[i] and f[(i + 1) // 2]:
        c[i] += 1
for i in range(3, MAX):
    c[i] += c[i - 1]

Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((c[r] - c[l - 1]))
# Original solution
max_lr = 10 ** 5

sieve = [True] * (max_lr + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, max_lr + 1):
    if not sieve[i]:
        continue
    for j in range(i * i, max_lr + 1, i):
        sieve[j] = False

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if sieve[i] and sieve[(i + 1) // 2]:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l - 1]))


# Optimized solution
from math import sqrt

max_lr = 10 ** 5

sieve = [True] * (max_lr + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, int(sqrt(max_lr)) + 1):
    if not sieve[i]:
        continue
    for j in range(i * i, max_lr + 1, i):
        sieve[j] = False

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if sieve[i] and sieve[(i + 1) // 2]:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l - 1]))
# Original solution
# エラトステネスの篩, 累積和
def make_prime_table(N):
    sieve = [0] * (N + 1)
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, N + 1):
        if sieve[i] != 0:
            continue
        sieve[i] = i
        for j in range(i * i, N + 1, i):
            if sieve[j] == 0:
                sieve[j] = i
    return sieve

max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l - 1]))


# Optimized solution
# エラトステネスの篩, 累積和
def make_prime_table(N):
    sieve = list(range(N + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(N ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, N + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(eval(input()))
result = []
for _ in range(Q):
    l, r = list(map(int, input().split()))
    result.append(cs[r] - cs[l - 1])
print(('\n'.join(str(i) for i in result)))
# Original solution
# エラトステネスの篩, 累積和
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    j = (i + 1) // 2
    if prime_table[i] == i and prime_table[j] == j:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
#print('\n'.join(str(i) for i in result))
print(*result, sep='\n')


# Optimized solution
# エラトステネスの篩, 累積和
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


max_lr = 10 ** 5

prime_table = make_prime_table(max_lr)

cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    j = (i + 1) // 2
    if prime_table[i] == i and prime_table[j] == j:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]

Q = int(input())
result = []
for _ in range(Q):
    l, r = map(int, input().split())
    result.append(cs[r] - cs[l - 1])
print(*result, sep='\n')
# Original solution
def sb(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
num=[0]*(10**5+1)
num2=[0]*(10**5+1)
cnt=[0]*(10**5+1)
num[2]+=1
for i in range(2,10**5+1):
    if i%2==1:
        n=sb(i)
        if len(n)==1 and n[0][1]==1:
            num[i]+=1
        if num[i]==1 and num[(i+1)//2]==1:
            num2[i]+=1
for i in range(1,len(num2)):
    cnt[i]=cnt[i-1]+num2[i]
q=int(eval(input()))
for i in range(q):
    l,r=list(map(int,input().split()))
    print((cnt[r]-cnt[l-1]))


# Optimized solution
import math
q=int(eval(input()))
num=[0]*(10**5+5)
ans=[0]*(10**5+5)
num[2]=1
for i in range(3,10**5+2,2):
    yn=0
    for j in range(2,int(math.sqrt(i))+1):
        if i%j==0:
            yn=1
            break
    if yn==0:
        num[i]=1
        if num[(i+1)//2]==1:
            ans[i]=1
for i in range(1,len(num)):
    ans[i]=ans[i-1]+ans[i]
for i in range(q):
    l,r=list(map(int,input().split()))
    print((ans[r]-ans[l-1]))
# Original solution
import math
import bisect
def get_prime(number):
    prime_list = []
    search_list = list(range(2,number + 1))
    while search_list[0] <= math.sqrt(number):
        head_num = search_list.pop(0)
        prime_list.append(head_num)
        search_list = [num for num in search_list if num % head_num != 0]
    prime_list.extend(search_list)
    return prime_list

l = get_prime(100000)
l2 = []
for i in range(len(l)):
    x = l[i]
    y = (x+1)//2
    if y in l:
        l2.append(x)
        
Q = int(eval(input()))
for i in range(Q):
    a,b = list(map(int, input().split()))
    x = bisect.bisect_left(l2, a)
    y = bisect.bisect_right(l2, b)
    print((y-x))


# Optimized solution
def prime_factor_table(n):
    table = [0] * (n + 1)

    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i

    return table

l = prime_factor_table(100000)
l[0] = 1
l[1] = 1
l2 = [0]*100000

for i in range(1,100000,2):
    x = (i+1)//2
    if l[i] == 0 and l[x] == 0:
        l2[i] = 1

l3 = [0]
for i in range(100000):
    x = l3[i] + l2[i]
    l3.append(x)

Q = int(eval(input()))
for i in range(Q):
    a,b = list(map(int, input().split()))
    print((l3[b+1]-l3[a]))
# Original solution
import math
Q = int(eval(input()))

li = [0]
cnt = 0
for i in range(3, 10**5+1, 2):
  flag = True
  for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
      flag = False
  for j in range(2, int(math.sqrt((i+1)//2)+1)):
    if ((i+1)//2) % j == 0:
      flag = False
  if flag:
    cnt += 1
  li.append(cnt)
  
for i in range(Q):
  l, r = list(map(int, input().split()))
  if l == 1:
    ans = li[r//2]
  else:
    ans = li[r//2] - li[l//2-1]
  print(ans)

# Optimized solution
import math
Q = int(eval(input()))

li = [0]
cnt = 0
for i in range(3, 10**5+1, 2):
  flag = True
  for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
      flag = False
  if flag:
    for j in range(2, int(math.sqrt((i+1)//2)+1)):
      if ((i+1)//2) % j == 0:
        flag = False
  if flag:
    cnt += 1
  li.append(cnt)
  
for i in range(Q):
  l, r = list(map(int, input().split()))
  if l == 1:
    ans = li[r//2]
  else:
    ans = li[r//2] - li[l//2-1]
  print(ans)