Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03074 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b = LI()
    if a == b:
        print(2*a)
    else:
        print(2*max(a,b)-1)
    return

#B
def B():
    n = I()
    h = LI()
    m = h[0]
    ans = 1
    for i in range(1,n):
        if m <= h[i]:
            ans += 1
            m = h[i]
    print(ans)
    return

#C
def C():
    s = S()
    ans = 0
    n = len(s)
    t = ["1" if i%2 else "0" for i in range(n)]
    for i in range(n):
        if t[i] != s[i]:
            ans += 1
    ans2 = 0
    t = ["0" if i%2 else "1" for i in range(n)]
    for i in range(n):
        if t[i] != s[i]:
            ans2 += 1
    print(min(ans,ans2))
    return

#D
def D():
    n,k = LI()
    s = S()
    f = [0 for i in range(n)]
    if s[0] == "0":
        f[0] = 1
    for i in range(1,n):
        if s[i] ==  "0" and s[i-1] == "1":
            f[i] = 1
    for i in range(n-1):
        f[i+1] += f[i]
    ans = 0
    for l in range(n):
        r = bisect.bisect_right(f,k+f[l]*int(s[l]))
        ans = max(ans, r-l)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    D()

Buggy submission (verdict: Runtime Error):
import bisect;n,k=map(int,input().split());s=input();f=[0]*n;f[0]=1-int(s[0])
for i in range(1,n):f[i]=(1-int(s[i]))*int(s[i-1])
for i in range(n-1):f[i+1]+=f[i];a=0
for l in range(n):r=bisect.bisect_right(f,k+f[l]*int(s[l]));a=max(a,r-l)
print(a)

Buggy submission (verdict: Runtime Error):
import bisect
n,k=map(int,input().split())
s=input()
f=[0 for i in range(n)]
f[0]=1-int(s[0])
for i in range(1,n):f[i]=(1-int(s[i]))*(s[i-1]^s[i])
for i in range(n-1):f[i+1]+=f[i]
ans=0
for l in range(n):
    r=bisect.bisect_right(f,k+f[l]*int(s[l]))
    ans=max(ans,r-l)
print(ans)
Problem p03086 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n = input()
    if n == "A":
        print("T")
    elif n == "C":
        print("G")
    elif n == "G":
        print("C")
    else:
        print("A")
    return

#B
def B():
    s = S()
    ans = 0
    n = len(s)
    for i in range(n):
        for j in range(i,n):
            f = 1
            for k in range(i,j+1):
                if s[k] not in list("AGCT"):f = 0
            if f:
                ans = max(ans,j+1-i)
    print(ans)
#C
def C():
    n,q = LI()

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Buggy submission (verdict: Runtime Error):
n = input();ans="ACGT";k=ans.index(n)^3;print(ans[k])
Problem p03136 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
t,x = LI()
print(t/x)
"""

#B
n = II()
a = LI()
m = max(a)
if m >= sum(a)-m:
    print("No")
else:
    print("Yes")
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
#A
def A():
    t,x = LI()
    print(t/x)

#B
def B():
    n= II()
    a = LI()
    m = max(a)
    if m >= sum(a)-m:
        print("No")
    else:
        print("Yes")


#C
def C():
    n,m = LI()
    x = LI()
    x.sort()
    l = [x[i+1]-x[i] for i in range(m-1)]
    l.sort()
    l = l[::-1]
    ans = sum(l[max(n-1,0):])
    print(ans)

#D
def D():
    n,k = LI()
    a = LI()
    k = list(map(int,list(bin(k)[2:])))
    l = len(k)
    for i in range(n):
        a[i] = list(map(int,list(bin(a[i])[2:])))
        l = max(l,len(a[i]))
    for i in range(n):
        for j in range(l-len(a[i])):
            a[i].insert(0,0)
    for j in range(l-len(k)):
        k.insert(0,0)
    s = [[0,0] for i in range(l)]
    pow2 = [1 for i in range(l)]
    for i in range(l-1)[::-1]:
        pow2[i] = pow2[i+1]*2
    for i in a:
        for j in range(l):
            s[j][0] += pow2[j]*i[j]
            s[j][1] += pow2[j]*(not i[j])
    dp = [0 for i in range(l+1)]
    small = False
    for i in range(l):
        if not small:
            if not k[i]:
                dp[i+1] += dp[i]+s[i][0]
            else:
                if s[i][0] >= s[i][1]:
                    dp[i+1] += dp[i]+s[i][0]
                    small = True
                else:
                    dp[i+1] += dp[i]+s[i][1]
        else:
            dp[i+1] += dp[i]+max(s[i])
    print(dp[l])

#E
if __name__ == "__main__":
    B()

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T
Problem p03260 (python)

Fixed submission:
a,b = map(int, input().split())
if a*b %2 == 1:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b,c = LI()
    print(9*max(a,b,c)+a+b+c)
    return

#B
def B():
    a,b = LI()
    if a*b %2:
        print("Yes")
    else:
        print("No")
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    A()
Problem p03267 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    l = I()
    l = list(map(int,bin(l)[2:]))
    n = len(l)
    ans = []
    for i in range(n-1):
        ans.append((i+1,i+2,0))
        ans.append((i+1,i+2,1<<i))
    w = (1<<(n-1))
    for i in range(1,n):
        if l[i]:
            x = n-i
            ans.append((x,n,w))
            w += (1<<(x-1))
    print(n,len(ans))
    for x,y,w in ans:
        print(x,y,w)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Buggy submission (verdict: Runtime Error):
l=int(input());b=bin(l)[2:];n=len(b);print(n,2*n+b.count("1")-3)
for i in range(1,n):print(i,i+1,0);print(i,i+1,1<<(i-1))if b[n-i]=="1":print(i,n,l);l-=1<<(i-1)

Buggy submission (verdict: Runtime Error):
l=bin(int(input()))[2:];n=len(l);print(n,2*n+l.count("1")-3)
for i in range(1,n):print(i,i+1,0);print(i,i+1,1<<(i-1))
w=1<<(n-1)
for i in range(1,n)[::-1]:
 　if l[n-i]=="1":print(i,n,w);w+=1<<(i-1)
Problem p03274 (python)

Fixed submission:
import bisect

n,k = map(int, input().split())
x = list(map(int, input().split()))
j = bisect.bisect_right(x,0)
if x[-1] > 0:
    j += 1
ans = float("INF")
for i in range(max(j-1-k,0), max(min(j,n-k+1),0)):
    key = x[i+k-1]-x[i]
    ans = min(ans, min(abs(x[i])+key, abs(x[i+k-1])+key))
print(ans)

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    c = s.count("0")
    print(2*min(c,len(s)-c))
    return

#B
def B():
    n = I()
    h = LI()
    ans = 0
    m = min(h)
    while m:
        ans += m
        k = max(h)
        for i in range(n):
            if h[i] >= m:
                h[i] -= m
                if h[i]:k = min(k,h[i])
            else:break
        m = k
    print(ans)
    return

#C
def C():
    n,k = LI()
    x = LI()
    ans = float("inf")
    j = bisect.bisect_left(x,0)
    if n == 1:
        print(abs(x[0]))
        quit()
    if x[j] == 0:
        k -= 1
        x.pop(j)
        n -= 1
    for i in range(n):
        if i < j:
            if abs(i-j) > k:continue
            elif abs(i-j) == k:ans = min(ans,abs(x[i]))
            elif k+i-1 < n:
                ans = min(ans,abs(x[i])+x[k+i-1]-x[i])
        else:
            if abs(i-j)+1 > k:continue
            elif abs(i-j)+1 == k:ans = min(ans,x[i])
            elif i-k+1 >= 0:
                ans = min(ans,abs(x[i])+x[i]-x[i-k+1])

    print(ans)
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    C()
Problem p03284 (python)

Fixed submission:
n,k = map(int, input().split())
print(0 if n%k == 0 else 1)

Buggy submission (verdict: Runtime Error):
n = int(input())
for i in range(16):
    if n%4 == 0:
        print("Yes")
        quit()
    n -= 7
    if n < 0:
        break
print("No")
Problem p03296 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
ans = 0
key = False
for i in range(1,n):
    if a[i] == a[i-1] and not key:
        ans += 1
        key = True
    else:
        key = False
print(ans)

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    for i in range(n>>1):
      s[i],s[n-i-1] = s[n-i-1],s[i]
    d = defaultdict(lambda : 0)
    m = 1<<n
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&(1<<j):
                r.append(s[j])
            else:
                b.append(s[j])
        d[(tuple(r),tuple(b))] += 1
        
    ans = 0
    for i in range(m):
        r = []
        b = []
        for j in range(n):
            if i&(1<<j):
                r.append(s[j+n])
            else:
                b.append(s[j+n])
        ans += d[(tuple(r),tuple(b))]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()
Problem p03311 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    a = LI()
    for i in range(n):
        a[i] -= i+1
    a.sort()
    b = sum(a)//n
    ans = 0
    for i in range(n):
        ans += abs(a[i]-b)
    ans2 = 0
    b += 1
    for i in range(n):
        ans2 += abs(a[i]-b)
    ans3 = 0
    b = a[n//2]
    for i in range(n):
        ans3 += abs(a[i]-b)
    print(min(ans,ans2,ans3))

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

n = I()
a = LI()
for i in range(n):
    a[i] -= i+1
a.sort()
b = a[n>>1]
ans = 0
for i in a:
    ans += abs(i-b)
if n%2:
    b = a[(n>>1)+1]
    ans_ = 0
    for i in a:
        ans_ += abs(i-b)
    if ans > ans_:
        ans = ans_
    b = (a[(n>>1)+1]+a[n>>1])>>1
    ans_ = 0
    for i in a:
        ans_ += abs(i-b)
    if ans > ans_:
        ans = ans_
print(ans)
Problem p03351 (python)

Fixed submission:
a,b,c,d = map(int, input().split())
if abs(a-b) <= d and abs(b-c) <= d:
    print("Yes")
    quit()
if abs(a-c) <= d:
    print("Yes")
    quit()
print("No")

Buggy submission (verdict: Runtime Error):
import itertools
n,m = map(int, input().split())
p = list(map(int, input().split()))
x_y = [list(map(int, input().split())) for i in range(m)]
key = [i for i in range(m)]
sum = 0
for i in range(n):
    if i+1==p[i]:
        sum += 1
if sum == n:
    print(sum)
    quit()
update = True
while update:
    update = False
    i = 1
    while i < len(x_y):
        for j in range(len(x_y[i])):
            if x_y[i][j] in x_y[i-1]:
                update = True
                key[i] = key[i-1]
                x_y[i-1] += x_y[i]
                x_y[i-1] = list(set(x_y[i-1]))
                if len(x_y) == 1:
                    break
                del x_y[i]
                i -= 1
        i += 1
lis = []
for i in x_y:
    if len(i) != 0:
        lis += list(itertools.permutations(i))

for i in lis:
    i = list(i)
    v = [i+1 for i in range(n)]
    for j in i:
        v.remove(j)
    for j in v:
        i.insert(j-1,j)
    count = 0
    for j in range(len(i)):
        if j+1 == p[i[j]-1]:
            count += 1
    sum = max(sum, count)
print(sum)

Buggy submission (verdict: Runtime Error):
s = input()
k = int(input())
dic = {}
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        if s[i:j] in dic:
            continue
        dic[s[i:j]] = 1

print(sorted(dic.keys())[k-1])
Problem p03363 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    a = LI()
    for i in range(n-1):
        a[i+1] += a[i]
    a.insert(0,0)
    f = defaultdict(lambda : 0)
    ans = 0
    for i in a:
        ans += f[i]
        f[i] += 1
    print(ans)
    return
#B
def B():

    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    A()

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
s = [0 for i in range(n+1)]
sum = 0
for i in range(n):
    sum += a[i]
    s[i+1] = sum
s.sort()
ans = 0
for i in range(1,n+1):
    if s[i] == s[i-1]:
        j = i-1
        while s[i] == s[j]:
            ans += 1
            j -= 1
print(ans)
Problem p03415 (python)

Fixed submission:
ans = ""
data = ["", "", ""]
for i in range(3):
    data[i] = input("")
    ans += data[i][i]
print(ans)

Buggy submission (verdict: Runtime Error):
data = input()
data = data.split(" ")
n = int(data[0])
m = int(data[1])
if n>1 and m>1: print(n*m-2*(n+m)+4)
elif n=1 and m=1: print(1)
else: print(n*m-2)
Problem p03417 (python)

Fixed submission:
data = input()
data = data.split(" ")
n = int(data[0])
m = int(data[1])
if n>1 and m>1: print(n*m-2*(n+m)+4)
elif n==1 and m==1: print(1)
else: print(n*m-2)

Buggy submission (verdict: Runtime Error):
data = input()
data = data.split(" ")
n = int(data[0])
m = int(data[1])
if n>1 and m>1: print(n*m-2*(n+m)+4)
elif n=1 and m=1: print(1)
else: print(n*m-2)
Problem p03476 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(100001)]
    for i in range(1,100001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l-1])

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(10001)]
    for i in range(1,10001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l-1])

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()