import sys

# import collections

# import math

# import bisect

# import re

# import itertools





def primeNums(n):

    from math import floor, sqrt

    sieve = set(range(2, n + 1))

    if 2 in sieve:

        not_prime = set(range(2 * 2, n + 1, 2))

        sieve -= not_prime

    for i in range(3, floor(sqrt(n)) + 1, 2):

        if i in sieve:

            not_prime = set(range(i * 2, n + 1, i))

            sieve -= not_prime

    return sieve



limit = 10 ** 5

prime_table = [0 for _ in range(limit + 1)]

for p in primeNums(limit):

    prime_table[p] = 1



like_2017_table = [0 for _ in range(limit + 1)]

for i in range(3, limit + 1, 2):

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

            like_2017_table[i] = 1



s = [0 for _ in range(limit + 1)]

for i in range(limit):

    s[i+1] = s[i] + like_2017_table[i+1]



def main():



    q = int(sys.stdin.readline().rstrip())

    m = list(map(int, sys.stdin.read().split()))



    for l, r in zip(m, m):

        res = s[r] - s[l-1]

        print(res)





if __name__ == "__main__":

    main()

import sys

from math import floor, sqrt



def prime_nums(n):

    sieve = set(range(2, n + 1))

    non_prime = set(range(2 * 2, n + 1, 2))

    sieve -= non_prime

    for i in range(3, floor(sqrt(n)) + 1, 2):

        if i in sieve:

            non_prime = set(range(i * 2, n + 1, i))

            sieve -= non_prime

    return sieve



p = prime_nums(10**5)



cnt = [None] * (10**5+1)

cnt[0] = 0

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

    if i in p and (i + 1) // 2 in p:

        cnt[i] = cnt[i-1] + 1

    else:

        cnt[i] = cnt[i-1]

    cnt[i+1] = cnt[i]



q = int(sys.stdin.readline().rstrip())

lr = zip(*[map(int, sys.stdin.read().split())] * 2)



def main():

    for l, r in lr:

        yield cnt[r] - cnt[l-1]

    

if __name__ == '__main__':

    ans = main()

    print(*ans, sep='\n')

import sys

# import collections
# import math
# import bisect
# import re
# import itertools
def primeNums(n):
    from math import floor, sqrt

    sieve = set(range(2, n + 1))
    if 2 in sieve:
        not_prime = set(range(2 * 2, n + 1, 2))
        sieve -= not_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            not_prime = set(range(i * 2, n + 1, i))
            sieve -= not_prime
    return sieve


limit = 10**5
prime_table = [0 for _ in range(limit + 1)]
for p in primeNums(limit):
    prime_table[p] = 1
like_2017_table = [0 for _ in range(limit + 1)]
for i in range(3, limit + 1, 2):
    if prime_table[i] and prime_table[(i + 1) // 2]:
        like_2017_table[i] = 1
s = [0 for _ in range(limit + 1)]
for i in range(limit):
    s[i + 1] = s[i] + like_2017_table[i + 1]


def main():
    q = int(sys.stdin.readline().rstrip())
    m = list(map(int, sys.stdin.read().split()))
    for l, r in zip(m, m):
        res = s[r] - s[l - 1]
        print(res)


if __name__ == "__main__":
    main()

import sys
from math import floor, sqrt


def prime_nums(n):
    sieve = set(range(2, n + 1))
    non_prime = set(range(2 * 2, n + 1, 2))
    sieve -= non_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            non_prime = set(range(i * 2, n + 1, i))
            sieve -= non_prime
    return sieve


p = prime_nums(10**5)
cnt = [None] * (10**5 + 1)
cnt[0] = 0
for i in range(1, 10**5 + 1, 2):
    if i in p and (i + 1) // 2 in p:
        cnt[i] = cnt[i - 1] + 1
    else:
        cnt[i] = cnt[i - 1]
    cnt[i + 1] = cnt[i]
q = int(sys.stdin.readline().rstrip())
lr = zip(*[map(int, sys.stdin.read().split())] * 2)


def main():
    for l, r in lr:
        yield cnt[r] - cnt[l - 1]


if __name__ == "__main__":
    ans = main()
    print(*ans, sep="\n")

+from math import floor, sqrt -# import collections -# import math -# import bisect -# import re -# import itertools -def primeNums(n): -    from math import floor, sqrt +def prime_nums(n): -    if 2 in sieve: -        not_prime = set(range(2 * 2, n + 1, 2)) -        sieve -= not_prime +    non_prime = set(range(2 * 2, n + 1, 2)) +    sieve -= non_prime -            not_prime = set(range(i * 2, n + 1, i)) -            sieve -= not_prime +            non_prime = set(range(i * 2, n + 1, i)) +            sieve -= non_prime -limit = 10**5 -prime_table = [0 for _ in range(limit + 1)] -for p in primeNums(limit): -    prime_table[p] = 1 -like_2017_table = [0 for _ in range(limit + 1)] -for i in range(3, limit + 1, 2): -    if prime_table[i] and prime_table[(i + 1) // 2]: -        like_2017_table[i] = 1 -s = [0 for _ in range(limit + 1)] -for i in range(limit): -    s[i + 1] = s[i] + like_2017_table[i + 1] +p = prime_nums(10**5) +cnt = [None] * (10**5 + 1) +cnt[0] = 0 +for i in range(1, 10**5 + 1, 2): +    if i in p and (i + 1) // 2 in p: +        cnt[i] = cnt[i - 1] + 1 +    else: +        cnt[i] = cnt[i - 1] +    cnt[i + 1] = cnt[i] +q = int(sys.stdin.readline().rstrip()) +lr = zip(*[map(int, sys.stdin.read().split())] * 2) -    q = int(sys.stdin.readline().rstrip()) -    m = list(map(int, sys.stdin.read().split())) -    for l, r in zip(m, m): -        res = s[r] - s[l - 1] -        print(res) +    for l, r in lr: +        yield cnt[r] - cnt[l - 1] -    main() +    ans = main() +    print(*ans, sep="\n")