abc 084 d

10**5までの素数のリストをどう作るのが早いかという話。
とりあえず python 素数判定 高速 でググってこれをコピペしてみた。ミラーテストというらしい。
Pythonを使って高速素数判定をしてみる - Pashango’s Blog
k = 13 のときで 1700ms だった。 4**13分の１で間違えるらしい。
次にエラトステネスの篩を使った。1413ms とちょっと早い。
色々考えて、とりあえずフェルマーテストして、そこから素数ではないけど弾かれない疑素数だけ強引に取り除いたらいいのではとなり、１０万まで限定で高速に素数のリストを作る不器用なコードが完成した。483ms くらいまで早くなった。
一応説明すると、5と7でフェルマーテストして、素数だけど弾かれる 5,7 を先に入れて、弾かれない
561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831 を強引に引くという戦法

def is_prime(q):
    if q < 2 or q&1 == 0: return False
    return pow(5, q-1, q)*pow(7, q-1, q) == 1
  
def main():
  s = set([561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831])
  b = [2,5,7]
  for i in range(2,10**5):
    if i in s:
      continue
    if is_prime(i):
      b.append(i)

  a = set([2*i-1 for i in b])
  b = set(b)
  chk = sorted(tuple(a&b))

  from bisect import bisect,bisect_left
  import sys
  input = sys.stdin.readline

  q = int(input())
  for i in range(q):
    l,r = map(int,input().split())
    print(bisect(chk,r)-bisect_left(chk,l))
    
if __name__ == '__main__':
    main()