q = int(eval(input()))

ll = []

rr = []

for i in range(q):

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

    ll.append(l)

    rr.append(r)



m = min(ll)

M = max(rr)

cnt = [0]*(M+2)



def is_prime(n):

    if n == 1:

        return False

    for i in range(2,int(n**0.5)+1):

        if n%i == 0:

            return False

    return True



s = 0

for i in range(m,M+1,2):

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

        s += 1

    cnt[i] = s



for i in range(q):

    print((cnt[rr[i]]-cnt[ll[i]-2]))
q = int(eval(input()))

ll = []

rr = []

for i in range(q):

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

    ll.append(l)

    rr.append(r)



def f(n):

    flag = [True]*(n+1)

    flag[0] = flag[1] = False

    for i in range(2,int(n**0.5)+1):

        if flag[i]:

            x = 2*i

            while x <= n:

                flag[x] = False

                x += i

    return flag



m = max(rr)

j = f(m)

cnt = [0]*(m+1)

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

    cnt[i] = cnt[i-1]

    if i%2 != 0 and j[i] and j[(i+1)//2]:

        cnt[i] += 1



for i in range(q):

    print((cnt[rr[i]]-cnt[ll[i]-1]))
q = int(eval(input()))
ll = []
rr = []
for i in range(q):
    l, r = list(map(int, input().split()))
    ll.append(l)
    rr.append(r)
m = min(ll)
M = max(rr)
cnt = [0] * (M + 2)


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True


s = 0
for i in range(m, M + 1, 2):
    if is_prime(i) and is_prime((i + 1) // 2):
        s += 1
    cnt[i] = s
for i in range(q):
    print((cnt[rr[i]] - cnt[ll[i] - 2]))

q = int(eval(input()))
ll = []
rr = []
for i in range(q):
    l, r = list(map(int, input().split()))
    ll.append(l)
    rr.append(r)


def f(n):
    flag = [True] * (n + 1)
    flag[0] = flag[1] = False
    for i in range(2, int(n**0.5) + 1):
        if flag[i]:
            x = 2 * i
            while x <= n:
                flag[x] = False
                x += i
    return flag


m = max(rr)
j = f(m)
cnt = [0] * (m + 1)
for i in range(1, m + 1):
    cnt[i] = cnt[i - 1]
    if i % 2 != 0 and j[i] and j[(i + 1) // 2]:
        cnt[i] += 1
for i in range(q):
    print((cnt[rr[i]] - cnt[ll[i] - 1]))

-m = min(ll) -M = max(rr) -cnt = [0] * (M + 2) -def is_prime(n): -    if n == 1: -        return False +def f(n): +    flag = [True] * (n + 1) +    flag[0] = flag[1] = False -        if n % i == 0: -            return False -    return True +        if flag[i]: +            x = 2 * i +            while x <= n: +                flag[x] = False +                x += i +    return flag -s = 0 -for i in range(m, M + 1, 2): -    if is_prime(i) and is_prime((i + 1) // 2): -        s += 1 -    cnt[i] = s +m = max(rr) +j = f(m) +cnt = [0] * (m + 1) +for i in range(1, m + 1): +    cnt[i] = cnt[i - 1] +    if i % 2 != 0 and j[i] and j[(i + 1) // 2]: +        cnt[i] += 1 -    print((cnt[rr[i]] - cnt[ll[i] - 2])) +    print((cnt[rr[i]] - cnt[ll[i] - 1]))