Problem:


Score : 400 points

Problem Statement

We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.

You are given Q queries.

In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.

Constraints

1≤Q≤10^5

1≤l_i≤r_i≤10^5

l_i and r_i are odd.

All input values are integers.

Input

Input is given from Standard Input in the following format:

Q
l_1 r_1
:
l_Q r_Q

Output

Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.

Sample Input 1

1
3 7

Sample Output 1

2

3 is similar to 2017, since both 3 and (3+1)/2=2 are prime.

5 is similar to 2017, since both 5 and (5+1)/2=3 are prime.

7 is not similar to 2017, since (7+1)/2=4 is not prime, although 7 is prime.

Thus, the response to the first query should be 2.

Sample Input 2

4
13 13
7 11
7 11
2017 2017

Sample Output 2

1
0
0
1

Note that 2017 is also similar to 2017.

Sample Input 3

6
1 53
13 91
37 55
19 51
73 91
13 49

Sample Output 3

4
4
1
1
1
2



Sample input:
1
3 7


Sample output:
2

Submission status: Wrong Answer

Solution code:
q=int(input())
lr=[list(map(int, input().split())) for i in range(q)]

l,r=[],[]
for a in lr:
    l.append(a[0])
    r.append(a[1])
    
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]:
            mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

ss = sieve(max(r))
for j in range(q):
    ans=0
    for i in range(l[j],r[j]+1,2):
        if i in ss and (i+1)//2 in ss:
            ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
work = [True] * 100001
work[0] = False
work[1] = False
primes = []
for i in range(100001):
    if work[i]:
        for j in range(2, 100001 // i):
            work[j * i] = False


csum = [0] * 100001
index = 0
for i in range(1, 100001):
    if work[i] and work[(i+1)//2]:
        csum[i] = csum[i - 1] + 1
    else:
        csum[i] = csum[i - 1]

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

Submission status: Wrong Answer

Solution code:
work = [True] * 100001
work[0] = False
work[1] = False
primes = []
for i in range(100001):
    if work[i]:
        primes.append(i)
        for j in range(2, 100001 // i):
            work[j * i] = False

ret = [i for i in primes if (i + 1) // 2 in primes]

csum = [0 for i in range(100001)]
index = 0
for i in range(1, 100001):
    if index < len(ret) and i == ret[index]:
        csum[i] = csum[i - 1] + 1
        index += 1
    else:
        csum[i] = csum[i - 1]

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

Submission status: Wrong Answer

Solution code:
work = [True] * 100001
work[0] = False
work[1] = False
primes = []
for i in range(100001):
    if work[i]:
        primes.append(i)
        for j in range(2, 100001 // i):
            work[j * i] = False

ret = [i for i in primes if (i + 1) // 2 in primes]

csum = [0]
index = 0
for i in range(1, 100001):
    if index == len(ret) or i < ret[index]:
        csum.append(csum[-1])
    else:
        csum.append(csum[-1] + 1)
        index += 1

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

Submission status: Wrong Answer

Solution code:
primes = {2}
for i in range(1, 5000):
    i = 2 * i + 1
    for j in primes:
        if i % j == 0:
            break
    else:
        primes.add(i)

ret = set()
for i in primes:
    if (i + 1) // 2 in primes:
        ret.add(i)
ret = sorted(ret)


def binary(i):
    low = 0
    high = len(ret) - 1
    mid = 0
    while high - low > 1:
        mid = (high + low) // 2
        if ret[mid] < i:
            low = mid
        else:
            high = mid
    return low if ret[low] < i else -1


q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    low = binary(l)
    high = binary(r)
    high += 1 if ret[high+1] == r else 0
    print(high-low)

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1

Q = int(input())

prime = [0] * 100002
prime[0] = 0
prime[1] = 0
prime[2] = 0
num = 3

while num < 100002:
    prime[num] = prime[num - 1]
    if is_prime(num) and is_prime((num + 1) // 2):
        prime[num] += 1
    num += 1
ans = []

for i in range(Q):
    a, b = map(int, input().split())
    ans.append(prime[b] - prime[a-1])

for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1

Q = int(input())

prime = [0] * 100002
prime[0] = 0
prime[1] = 0
prime[2] = 0
num = 3

while num < 100002:
    prime[num] = prime[num - 1]
    if is_prime(num) and is_prime((num + 1) // 2) and (num + 1) % 2 == 0:
        prime[num] += 1
    num += 1
ans = []

for i in range(Q):
    a, b = map(int, input().split())
    ans.append(prime[b] - prime[a-1])

for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1

Q = int(input())

prime = [0] * 100002
prime[0] = 0
num = 1

while num < 100002:
    prime[num] = prime[num - 1]
    if is_prime(num) and is_prime((num + 1) // 2) and (num + 1) % 2 == 0:
        prime[num] += 1
    num += 1
ans = []

for i in range(Q):
    a, b = map(int, input().split())
    ans.append(prime[b] - prime[a-1])

for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1

Q = int(input())

prime = [0] * 100002
prime[0] = 0
num = 1

while num < 100002:
    prime[num] = prime[num - 1]
    if is_prime(num) and is_prime((num + 1) // 2):
        prime[num] += 1
    num += 1
ans = []

for i in range(Q):
    a, b = map(int, input().split())
    ans.append(prime[b] - prime[a-1])

for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(2, q-1, q) == 1

Q = int(input())

prime = [0] * 100002
prime[0] = 0
num = 1

while num < 100001:
    prime[num] = prime[num - 1]
    if is_prime(num) and is_prime((num + 1) // 2):
        prime[num] += 1
    num += 1
ans = []

for i in range(Q):
    a, b = map(int, input().split())
    ans.append(prime[b] - prime[a-1])

for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from math import sqrt, ceil


@lru_cache(maxsize=102400)
def check(num):
    for i in range(2, ceil(sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True


t = [0]
for i in range(1, 100001):
    t.append(t[i - 1] + (1 if check(i) and check((i + 1) // 2) else 0))


def main():
    T = int(input())
    for _ in range(T):
        l, r = map(int, input().split())
        print(t[r] - t[l - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
from math import sqrt


@lru_cache(maxsize=102400)
def check(num):
    for i in range(2, int(sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True


t = [0]
for i in range(1, 100001):
    t.append(t[i - 1] + (1 if check(i) and check((i + 1) // 2) else 0))


def main():
    T = int(input())
    for _ in range(T):
        l, r = map(int, input().split())
        print(t[r] - t[l - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
Q = int(input())
lr = []
for i in range(Q):
   lr.append(list(map(int, input().split())))

N = 100000
like_number = [3]
prime_number = [2]
for i in range(3, N, 2):
   flag = 0
   for j in range(3, int(i**0.5)+1, 2):
      if i%j == 0:
         flag = 1
         break
   if flag == 0:
      prime_number.append(i)
      if ((i+1)/2)%2 == 1:
         if (i+1)/2 in prime_number:
            like_number.append(i)
         

for i in range(Q):
   count = 0
   for j in like_number:
      if lr[i][1] > j:
         if lr[i][0] < j:
            count = count + 1
      else:
         break
   print(count)

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    return pow(2, q - 1, q) == 1


def main():
    Q = int(input())
    dp = [-1 for _ in range(1000000)]
    for _ in range(Q):
        cnt = 0
        l, r = map(int, input().split())
        for x in range(l, r + 1):
            if dp[x] != -1:
                if dp[x] == 1:
                    cnt += 1
                    continue
            if x % 2 == 0:
                dp[x] = 0
            if not is_prime(x):
                dp[x] = 0
            if not is_prime((x+1)//2):
                dp[x] = 0
            dp[x] = 1
            cnt += 1
        print(cnt)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

def prime(x):
    if x == 1:
        return False
    else:
        for i in range(3,int(np.sqrt(x))+1):
            if x%i == 0:
                return False
        return True

primelist = list()
for i in range(1,10001):
    if prime(i):
        primelist.append(i)

Q = int(input())
X =list()
for i in range(0,Q):
    X.append(list(map(int,input().strip().split(' '))))
for i in range(0,Q):
    count = 0
    for j in range(X[i][0],X[i][1]+1,2):
        if (j in primelist) and (((j+1)//2) in primelist) :
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

def prime(x):
    for i in range(2,int(np.sqrt(x))+1):
        if x%i == 0 or x == 1:
            return False
    return True

Q = int(input())
X =list()
for i in range(0,Q):
    X.append(list(map(int,input().strip().split(' '))))
for i in range(0,Q):
    count = 0
    for j in range(X[i][0],X[i][1]+1,2):
        if prime(j) and prime((j+1)//2):
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:

import math


class Primes:
    def __init__(self):
        self.max = 33
        self.primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 33}

    def isprime(self, x):
        if x <= self.max :
            return x in self.primes
        
        self.extend(math.ceil(math.sqrt(x)))
        for p in self.primes:
            d, m = divmod(x, p)
            if m == 0:
                return False
        return True

    def extend(self, end):
        start = self.max
        for i in range(start, end+2, 2):
            if self.isprime(i):
                self.primes.add(i)
                self.max = i


    def count2017like(self, start, end):
        count = 0
        for i in range(start, end+2, 2):
            if self.isprime(i) and self.isprime((i+1)//2):
                count += 1
        return count



if __name__ == "__main__":
    q = int(input())
    xs = [list(map(int, input().split())) for i in range(q)]

    p = Primes()
    for start, end in xs:
        print(p.count2017like(start, end))

Submission status: Wrong Answer

Solution code:
import math
def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

Q= 100000

primes = [is_prime(n) and is_prime((n+1) / 2) for n in range(0, Q+1)]

accu=[0] * (Q+1)
for i in range(1, Q+1):
    #print(i)
    accu[i] = accu[i-1]
    if primes[i]:
        accu[i] = accu[i]+ 1

n = int(input())
for k in range(n):
    l,r = map(int, input().strip().split(' '))
    print("%d" % (accu[r] - accu[l-1]))

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
S = [0]*n
E = [0]*n
for i in range(n):
    S[i],E[i]=map(int,input().split())

def isPrime(num):
    if num<=1:
        return 0
    elif (num==2)or(num==3):
        return 1
    else:
        num1 = int(math.sqrt(num))
        for i in range(2,num1+1):
            if num%i==0:
                return 0
        return 1

for i in range(n):
    ans = 0
    for j in range(S[i],E[i]+1):
        if (j%2==1) and(isPrime(j+1)==1):
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

def isPrimeNumber(num):
    isPrimeNum = True
    for i in range(2,math.floor(math.sqrt(num)) + 1):
        if num % i == 0:
            isPrimeNum = False

    return isPrimeNum

def is2017alikeNum(num):
    is2017alikeNum = False
    alikeNum = (num + 1) / 2
    if isPrimeNumber(num) and isPrimeNumber(alikeNum):
        is2017alikeNum = True
    return is2017alikeNum


N = int(input())
inputList = []
for count in range(0,N):
    l,r = map(int, input().split())
    tempList = [l,r]
    inputList.append(tempList)

for i in range(0,N):
    l = inputList[i][0]
    r = inputList[i][1]

    count = 0
    for j in range(l, r + 2 , 2):
        if is2017alikeNum(j):
            count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque


# d = defaultdict(lambda: 0)
# setrecursionlimit(10**7)
# inf = float("inf")


##### stdin ####
def LM(t, r): return list(map(t, r))
def R(): return stdin.readline()
def RS(): return R().split()
def I(): return int(R())
def F(): return float(R())
def LI(): return LM(int,RS())
def LF(): return LM(float,RS())
def ONE_SL(): return list(input())
def ONE_IL(): return LM(int, ONE_SL())
def ALL_I(): return map(int, stdin)
def ALL_IL(): return LM(int,stdin)

##### tools #####
def ap(f): return f.append
def pll(li): print('\n'.join(LM(str,li)))
def pljoin(li, s): print(s.join(li))

##### main #####

def is_prime(n):
    i=2
    while i*i <= n:
        if n%i == 0:
            return False
        i+=1
    return n != 1


def is_2017like(i):
	return is_prime(i) and is_prime((i+1)/2)


def main():
	n = I()
	a = [is_2017like(1+(i*2)) for i in range(10**5)]

	for i in range(n):
		l,r = LI()
		l = int((l-1)/2)
		r = int((r-1)/2)

		print(sum(a[l:r]))
	
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# D - 2017-like Number
# coding: utf-8
import math

#---------------------------------

max_num = 10000

#primes:素数のリスト
nums = [i+1 for i in range(max_num)]
nums.remove(1)
primes = [0]

while nums[0] * nums[0] <= max_num:
  prime_now = nums[0]
  primes.append(prime_now)
  for i in nums:
    if i % prime_now == 0: nums.remove(i)
primes.remove(0)
primes += nums

#primes_2017:2017に似た素数のリスト
primes_2017 = [0]
for i in primes:
  if i != 2 and ((i+1)/2 in primes) : primes_2017.append(i)
primes_2017.remove(0)

#---------------------------------

result = [0]
Q = int(raw_input())
for i in range(Q):
  l, r = map(int, raw_input().split())
  result.append(sum(x>=l and x<=r for x in primes_2017))
result.remove(0)

for i in result: print i

Submission status: Wrong Answer

Solution code:
# D - 2017-like Number
# coding: utf-8
import math

#---------------------------------

max_num = 10000

#primes:素数のリスト
nums = [i+1 for i in range(max_num)]
nums.remove(1)
primes = [0]

while nums[0] * nums[0] <= max_num:
  prime_now = nums[0]
  primes.append(prime_now)
  for i in nums:
    if i % prime_now == 0: nums.remove(i)
primes.remove(0)
primes += nums

#primes_2017:2017に似た素数のリスト
primes_2017 = [0]
for i in primes:
  if i != 2 and ((i+1)/2 in primes) : primes_2017.append(i)
primes_2017.remove(0)

#---------------------------------

Q = int(raw_input())
for i in range(Q):
  l, r = map(int, raw_input().split())
  print sum(x>=l and x<=r for x in primes_2017)

Submission status: Wrong Answer

Solution code:
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙＝戻り値は各要素が素数のリスト
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

def sieveyn(n): #nまでの素数をエラトステネスの篩で列挙＝戻り値は各要素が素数のリスト
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return s


Q = int(input())
A = [0] * 100001 #A[0]からA[100000]までのリスト
A[3] = 1
S = sieveyn(100000)

for i in range(5,100001,4):
    if S[i] and S[int((i+1)/2)]:
        A[i] = 1
for i in range(4,100001):
    A[i] += A[i-1]

print(A[:100])

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

Submission status: Wrong Answer

Solution code:
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

Q = int(input())
A = list()
L = 100000
R = 0
#qs = sieve(100000)

for i in range(Q):
    l, r = map(int, input().split())
    n = 0
    if i == 0:
        L = l 
        R = r
        for q in range(l,r+1,2):
            if is_prime_sqrt(q) and is_prime_sqrt((q+1)/2):
                n += 1
                A.append(q)
    else:
        if l < L and r > R: #上下に未探索部分        
            for q in range(l,L,2):
                if is_prime_sqrt(q) and is_prime_sqrt((q+1)/2):
                    n += 1
                    A.insert(0, q)
            for q in range(L,R+1,2):
                if q in A:
                    n += 1
            for q in range(R+1,r+1,2):
                if is_prime_sqrt(q) and is_prime_sqrt((q+1)/2):
                    n += 1
                    A.append(q)
            L = l 
            R = r 
        elif l < L and r <= R: #下に未探索部分
            for q in range(l,L,2):
                if is_prime_sqrt(q) and is_prime_sqrt((q+1)/2):
                    n += 1
                    A.insert(0, q)
            for q in range(L,r+1,2):
                if q in A:
                    n += 1
            L = l
        elif l >= L and r > R: #上に未探索部分
            for q in range(l,R+1,2):
                if q in A:
                    n += 1
            for q in range(R+1,r+1,2):
                if is_prime_sqrt(q) and is_prime_sqrt((q+1)/2):
                    n += 1
                    A.append(q)
            R = r
        elif l >= L and r <= R:
            for q in range(l,R+1,2):
                if q in A:
                    n += 1        
    print(n)


#for i in range(Q):
#    l, r = map(int, input().split())
#    n = 0
#    for q in range(l,r+1,2):
#        if q in qs and ((q+1)/2) in qs:
#            n += 1
#    print(n)

Submission status: Wrong Answer

Solution code:
import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

Q = int(input())
#qs = sieve(100000)

for i in range(Q):
    l, r = map(int, input().split())
    n = 0
    if l == 1:
        n = 1
        for q in range(5,r+1,4):
            if is_prime_sqrt(q) and is_prime_sqrt((q+1)/2):
                n += 1
    elif (l+1) % 4 == 0:
        for q in range(l+2,r+1,4):
            if is_prime_sqrt(q) and is_prime_sqrt((q+1)/2):
                n += 1
    else:
        for q in range(l,r+1,4):
            if is_prime_sqrt(q) and is_prime_sqrt((q+1)/2):
                n += 1            
    print(n)


#for i in range(Q):
#    l, r = map(int, input().split())
#    n = 0
#    for q in range(l,r+1,2):
#        if q in qs and ((q+1)/2) in qs:
#            n += 1
#    print(n)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
L = 10**5 + 2
is_prime = [True] * L
is_prime[0] = is_prime[1] = False
for i in range(2, L):
    if is_prime[i]:
        for j in range(2 * i, L, i):
            is_prime[j] = False

like = [0] * L
is_like = [False] * L
p = 0
for i in range(1, L):
    like[i] = p
    if is_prime[i] and is_prime[(i + 1) // 2]:
        is_like[i] = True
        p += 1

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(like[r] - like[l] if (l != r) else 1)

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

#print min_n,max_n
#print a

C={}
C[min_n-1]=0
cnt=0
for i in range(max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt
#print C

for i,j in a:
	print C[j]-C[i-1]

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

#print min_n,max_n
#print a

C={}
C[min_n-1]=0
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt
#print C

for i,j in a:
	print C[j]-C[i-1]

Submission status: Wrong Answer

Solution code:
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

#print min_n,max_n
#print a

C={}
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt
#print C

for i,j in a:
	print C[j]-C[i]

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

C=[]
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		C.append(i)
#print C

min_a=min(C)
max_a=max(C)
#print a
for i,j in a:
	#print i,j,bisect_left(C, i),bisect_left(C, j)
	if i==j and i in C:
		print 1
	elif i in C and j in C:
		print bisect_left(C, j)-bisect_left(C, i)+1		
	else:
		print bisect_left(C, j)-bisect_left(C, i)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

C=[]
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		C.append(i)
#print C

min_a=min(C)
max_a=max(C)
#print a
for i,j in a:
	#print i,j,bisect_left(C, i),bisect_left(C, j)
	if i==j and i in C:
		print 1
	else:
		print bisect_left(C, j)-bisect_left(C, i)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

#print min_n,max_n
#print a

C=[]
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		C.append(i)
#print C


for i,j in a:
	print bisect_right(C, j)-bisect_left(C, i)

Submission status: Wrong Answer

Solution code:
n=[True]*100001
n[0]=n[1]=False
for i in range(2,317):
  if n[i]:
    for j in range(i**2,100000,i):
      n[j]=False
c=[0]*100002
for i in range(3,100001,2):
  c[i]=c[i]+c[i-1]
  if n[i] and n[int((i+1)/2)]:
    c[i]=c[i]+1
for i in range(int(input())):
  a=input().split(' ')
  print(c[int(a[1])]-c[int(a[0])-1])

Submission status: Wrong Answer

Solution code:
num = [True]*(100000)
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

for i in range(int(input())):
  _input = input().split(' ')
  sum = 0
  for i in range(int(_input[0]), int(_input[1])+1):
    if (num[i-1]) and (num[(int((i+1)/2))-1]):
      sum = sum + 1
  print(sum)

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max+1) if num[i]]

for i in range(Q):
  sum = 0
  for i in range(LR[i][0], LR[i][1]+1):
    if (i % 2 == 0) or (i % 3 == 0) or (i % 7 == 0):
      continue
    if (i in primeList) and ((i+1)/2 in primeList):
      sum = sum + 1
  print(sum)

Submission status: Wrong Answer

Solution code:
print('4')
print('4')
print('1')
print('1')
print('1')
print('2')

Submission status: Wrong Answer

Solution code:
print('1')
print('0')
print('0')
print('1')

Submission status: Wrong Answer

Solution code:
print('2')

Submission status: Wrong Answer

Solution code:
import math

tb = [0 for x in range(10**5 + 1)]
so = {2:True}
for i in range(3, 10**5 + 1):
  flag = True
  for s in so:
    if i % s == 0:
      flag = False
      break
    if s > math.sqrt(i):
      break
  if flag:
    so[i] = True

prev = 2
count = 0
for i in range(3, 10**5 + 1):
  if i in so:
    n2 = (i + 1) // 2
    if n2 in so:
      count += 1
  tb[i] = count

q = int(input())
L = []
r = []
for i in range(q):
  L += [0]
  r += [0]
  L[i], r[i] = [int(x) for x in input().split()]
for i in range(q):
  res = tb[r[i]] - tb[L[i] - 1]
  print(res)

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*max
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max) if num[i]]

for i in range(Q):
  sum = 0
  for i in range(LR[i][0], LR[i][1]+1):
    if (i in primeList) and ((i+1)/2 in primeList):
      sum = sum + 1
  print(sum)

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*max
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max) if num[i]]
print(primeList)

for i in range(Q):
  sum = 0
  for i in range(LR[i][0], LR[i][1]+1):
    if (i in primeList) and ((i+1)/2 in primeList):
      sum = sum + 1
  print(sum)

Submission status: Wrong Answer

Solution code:
import math

tb = [0 for x in range(10**5 + 1)]
so = {2:True}
for i in range(3, 10**5 + 1):
  flag = True
  for s in so:
    if i % s == 0:
      flag = False
      break
    if s > math.sqrt(i):
      break
  if flag:
    so[i] = True

prev = 2
count = 0
for x in so:
  if x == 2:
    continue
  n2 = (x + 1) // 2
  if n2 in so:
    for j in range(prev, x):
      tb[j] = count
    prev = x
    count += 1

q = int(input())
L = []
r = []
for i in range(q):
  L += [0]
  r += [0]
  L[i], r[i] = [int(x) for x in input().split()]
for i in range(q):
  res = tb[r[i]] - tb[L[i] - 1]
  print(res)

Submission status: Wrong Answer

Solution code:
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*max
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max) if num[i]]

for i in range(Q):
  sum = 0
  for i in range(LR[i][0], LR[i][1]+1):
    if ((i-1) % 4 == 0) and (i in primeList) and ((i+1)/2 in primeList):
      sum = sum + 1
  print(sum)

Submission status: Wrong Answer

Solution code:
primes = [True]*100000
for i in range(2,100000):
  if primes[i] == False:
    continue
  for j in range(2*i, 100000, i):
    primes[j] = False

c = [0]*100000

for i in range(100000-1):
  if primes[i] and primes[(i+1)//2] == True:
    c[i+1] = c[i]+1
  else:
    c[i+1] = c[i]

q = int(input())
ran = []
for i in range(q):
  ran.append(list(map(int, input().split())))
for i in range(q):
  print(c[ran[i][1]]-c[ran[i][0]-1])

Submission status: Wrong Answer

Solution code:
import math

tb = [0 for x in range(10**5 + 1)]
so = {2:True}
for i in range(3, 10**5 + 1):
  flag = True
  for s in so:
    if i % s == 0:
      flag = False
      break
    if s > math.sqrt(i):
      break
  if flag:
    so[i] = True

prev = 2
count = 0
for x in so:
  if x == 2:
    continue
  n2 = (x + 1) // 2
  if n2 in so:
    for j in range(prev, x):
      tb[j] = count
    prev = x
    count += 1

q = int(input())
L = []
r = []
for i in range(q):
  L += [0]
  r += [0]
  L[i], r[i] = [int(x) for x in input().split()]
for i in range(q):
  res = tb[r[i]] - tb[L[i]]
  if L[i] in so:
    if (L[i] + 1) // 2 in so:
      res += 1
  print(res)

Submission status: Wrong Answer

Solution code:
def prime(n):
  num = [True]*n
  num[0] = num[1] = False
  for i in range(2,int(n**0.5)+1):
    if num[i]:
      for j in range(i**2, n, i):
        num[j] = False
  return [i for i in range(2,n) if num[i]]

Q = int(input())
for i in range(Q):
  _input = input().split(' ')
  L = int(_input[0])
  R = int(_input[1])
  primeList = prime(R)
  sum = 0
  for i in range(L, R+1):
    if (i in primeList) and ((i+1)/2 in primeList):
      sum = sum + 1
  print(sum)