Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists,reverse=True)
from collections import Counter
dic=dict(Counter(lists))

ans=0
howmuch=[[] for i in range(30)]
for num in lists:
    c=0
    while num%2==0:
        num=num//2
        c+=1
    howmuch[c].append(num)
for i in range(30):
    if len(howmuch[i])<=1:
        pass
    else:
        dic=dict(Counter(howmuch[i]))
        for some in howmuch[i]:
            for j in range(1,30):
                if 2**j-some in dic.keys() and dic[some]>0 and dic[2**j-some]>0:
                    if some!=2**(j-1):
                        m=min(dic[some],dic[2**j-some])
                        dic[some]-=m
                        dic[2**j-some]-=m
                        ans+=m
                    elif some==2**(j-1):
                        ans+=dic[some]//2
                        dic[some]=dic[some]%2

print(ans)    
    
    
  

Fixed submission:

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
ans = 0

D = defaultdict(int)
for x in A:
    D[x] += 1
A.sort(reverse=True)

for x in A:
    for i in range(1, 31):
        if D[x] > 0:
            if 2**i-x in D.keys() and D[2**i-x] > 0:
                if 2**(i-1) != x:
                    ans += 1
                    D[x] -= 1
                    D[2**i-x] -= 1
for i in range(31):
    ans += D[2**i]//2
print(ans)
Buggy python submission (verdict: Runtime Error):
somelists=[]

for i in range(m):
    a,b=map(int,input().split())
    somelists.append([i,a,b])

somelists.sort(key=lambda x:(x[1],x[2]))

prefs=1
numbers=0

for x in somelists:
    
    if x[1]==prefs:
        numbers+=1
        
        x.append(numbers)
    if x[1]!=prefs:
        prefs=x[1]
        numbers=1
        x.append(numbers)

somelists.sort(key=lambda x:x[0])
for _ in range(m):
    print(str(somelists[_][1]).zfill(6)+str(somelists[_][3]).zfill(6))


Fixed submission:
n,m=map(int,input().split())
somelists=[]

for i in range(m):
    a,b=map(int,input().split())
    somelists.append([i,a,b])

somelists.sort(key=lambda x:(x[1],x[2]))

prefs=1
numbers=0

for x in somelists:
    
    if x[1]==prefs:
        numbers+=1
        
        x.append(numbers)
    if x[1]!=prefs:
        prefs=x[1]
        numbers=1
        x.append(numbers)

somelists.sort(key=lambda x:x[0])
for _ in range(m):
    print(str(somelists[_][1]).zfill(6)+str(somelists[_][3]).zfill(6))
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
maxi=0
cnt=1
while cnt<=m:
    if m%cnt==0:
        if m//cnt>=n:
            maxi=cnt
            cnt+=1
        else:
            cnt+=1     
    else:
        cnt+=1       
print(maxi)

Fixed submission:
n,m=map(int,input().split())
maxi=0
import math
num=math.sqrt(m)
nums=math.floor(num)

for i in range(1,nums+1):
    if m%i==0:
        number1=i
        number2=m//i
        #二つの約数について比べる
        #number1<number2
        #m//number1>m//number2
        if m//number1>=n and m//number2>=n:
            maxi=max(number2,maxi)
        elif m//number1>=n and m//number2<n:
            maxi=max(maxi,number1)
        
    else:
        continue
print(maxi)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
maxi=0
for i in range(1,m+1):
    if m%i==0 and m//i >=n:
        maxi=i
    else:
        continue   
        
print(maxi)
 

Fixed submission:
n,m=map(int,input().split())
maxi=0
import math
num=math.sqrt(m)
nums=math.floor(num)

for i in range(1,nums+1):
    if m%i==0:
        number1=i
        number2=m//i
        #二つの約数について比べる
        #number1<number2
        #m//number1>m//number2
        if m//number1>=n and m//number2>=n:
            maxi=max(number2,maxi)
        elif m//number1>=n and m//number2<n:
            maxi=max(maxi,number1)
        
    else:
        continue
print(maxi)
Buggy python submission (verdict: Runtime Error):
import math

n,k=map(int,input().split())
if k%2!=0:
  nums=math.ceil(n/k)
  print(nums*3)
 
else:
  nums1=math.ceil(2*n/k)
  if nums1%2==0:
    a=int(nums1/2)
    b=nums1-a
    print(a**3+b**3)
    
    
  elif nums1%2!=0:
    a=int((num-1)/2)
    b=nums1-a
    print(a**3+b**3)
      
  

Fixed submission:
import math

n,k=map(int,input().split())
if k%2!=0:
    nums=math.floor(n/k)
    print(nums**3)
 
else:
    nums1=math.floor(2*n/k)

    if nums1%2==0:
        a=int(nums1/2)
        b=nums1-a
        print(a**3+b**3)
    
    
    if nums1%2!=0:
        a=int((nums1+1)/2)
        b=nums1-a
        print(a**3+b**3)
Buggy python submission (verdict: Runtime Error):

a = [int(c) for c in s]
k=int(input())
strong=0
for some in range(k):
  if a[some]==1:
    strong+=1
  if strong==k-1:
    print(some)
  if a[some]!=1:
    print(some)
    break


Fixed submission:
s=input()
lists=[int(integer)for integer in s] 
nums=int(input())

numbers=0 
strong=0 
#sに位置が初め何個ついているのかをnumbers変数に代入する
#もしｓが1で始まらなかった場合、その初めの文字を出力して終了する
for j in lists:
    if lists[0]!=1:
        break
    else:
        if j==1:
            numbers+=1
        else:
            break
#startで場合分け            
if lists[0]==1:
    if numbers>=nums:
        print(1)
        
    elif numbers<nums:
        print(lists[numbers])
else:
    print(lists[0])
Buggy python submission (verdict: Time Limit Exceeded):
n,m,q=map(int,input().split())
data=[[0 for i in range(n+1)] for j in range(n+1)]
for _ in range(m):
    l,r=map(int,input().split())
    data[l][r]+=1

for _ in range(q):
    x,y=map(int,input().split())
    ans=0
    for i in range(x,y+1):
        for j in range(x,y+1):
            ans+=data[i][j]           
    print(ans)
    

Fixed submission:
n,m,q=map(int,input().split())
data=[[0 for i in range(n+1)] for j in range(n+1)]
for _ in range(m):
    l,r=map(int,input().split())
    data[l][r]+=1

for i in range(n+1):
    for j in range(1,n+1):
        data[i][j]+=data[i][j-1]
for i in range(n+1):
    for j in range(1,n+1):
        data[j][i]+=data[j-1][i]

for _ in range(q):
    x,y=map(int,input().split())
    print(data[y][y]-data[x-1][y]-data[y][x-1]+data[x-1][x-1])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
lists=list(map(int,input().split()))

for i in range(n):
    lists[i]-=(i+1)
mini=10**100
for k in range(-10**9,10**9):
    sub=0
    for _ in range(n):
        sub+=abs(lists[_]-k)
    mini=min(mini,sub)
           
print(mini)


Fixed submission:
n=int(input())
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
if n%2==0:
    num1=int(n/2-1)
    num2=int(n/2)
    numbers=min(uselist[num1],uselist[num2])
    
if n%2!=0:
    num1=int((n-1)/2)
    numbers=uselist[num1] 
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input().split())
lists=list(map(int,input().split())
for i in range(n):
    lists[i]-=(i+1)
mini=10**100
for k in range(-10**9,10**9,1):
    sub=0
    for i in range(n):
        sub+=abs(list[i]-k)
    mini=min(mini,sub)
           
print(mini)

Fixed submission:
n=int(input())
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
if n%2==0:
    num1=int(n/2-1)
    num2=int(n/2)
    numbers=min(uselist[num1],uselist[num2])
    
if n%2!=0:
    num1=int((n-1)/2)
    numbers=uselist[num1] 
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)

Buggy python submission (verdict: Runtime Error):
import bisect
n=int(input())
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
if n%2==0:
    num1=int(n/2-1)
    num2=int(n/2)
    numbers=min(uselist[num1],uselist[num2])
if n%2!=0:
    num1=int((n-1)/2)
    numbers=uselist[num1]  
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)

Fixed submission:
n=int(input())
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
if n%2==0:
    num1=int(n/2-1)
    num2=int(n/2)
    numbers=min(uselist[num1],uselist[num2])
    
if n%2!=0:
    num1=int((n-1)/2)
    numbers=uselist[num1] 
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n=int(input())
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
numbers=uselist[0]
while bisect.bisect_right(uselist,numbers)<n-bisect.bisect_right(uselist,numbers):
    numbers+=1
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)

Fixed submission:
n=int(input())
lists=list(map(int,input().split()))
uselists=[]
for _ in range(n):
    uselists.append(lists[_]-_-1)
uselist=sorted(uselists)
if n%2==0:
    num1=int(n/2-1)
    num2=int(n/2)
    numbers=min(uselist[num1],uselist[num2])
    
if n%2!=0:
    num1=int((n-1)/2)
    numbers=uselist[num1] 
ans=0
for x in range(n):
    ans+=abs(uselist[x]-numbers)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

def merge(L1, L2):
    P = []
    for x in L1:
        P.append(x)
    for y in L2:
        P.append(y)
    P.sort(reverse=True)
    return [P[0], P[1]]


def main():
    N = int(input())
    a = list(map(int, input().split()))
    dp = [[[0, -10**20] for j in range(N+1)]for i in range(1 << N)]
    for i in range(1 << N):
        dp[i][0][0] = a[i]

    for j in range(1, N+1):
        for i in range(1 << N):
            if (i & (1 << (j-1))):
                dp[i][j] = merge(dp[i & ~(1 << (j-1))][j - 1], dp[i][j-1])
            else:
                dp[i][j] = dp[i][j-1]
    result = [0]*(1 << N)
    for k in range(1, 1 << N):
        result[k] = max(result[k-1], sum(dp[k][N]))
        print(result[k])
    return


if __name__ == "__main__":
    main()



Fixed submission:
def merge(x, y, z, w):
    P = [x, y, z, w]
    P.sort()
    return P[-1], P[-2]


def main():
    N = int(input())
    a = list(map(int, input().split()))
    dp = [0]*(2*(N+1)*((1 << N)))

    def calc(i, j, k):
        return (2*N + 2) * i + (N+1)*k + j
    for i in range(1 << N):
        dp[calc(i, 0, 0)] = a[i]
    for j in range(1, N+1):
        for i in range(1 << N):
            x = calc(i, j, 0)
            y = calc(i & ~(1 << (j-1)), j - 1, 0)          
            if (i & (1 << (j-1))):
                dp[x], dp[x+N+1] = merge(dp[y], dp[y+N+1], dp[x-1], dp[x+N])
            else:
                dp[x], dp[x+N+1] = dp[x-1], dp[x+N]
    result = [0]*(1 << N)
    for k in range(1, 1 << N):
        result[k] = max(result[k-1], dp[calc(k, N, 0)]+dp[calc(k, N, 1)])
        print(result[k])
    return


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
copy=s[:]
lists=list(s)
orderlists=[]
for i in range(len(s)):
    for j in range(i,len(s)):
        if  "".join(lists[i:j+1]) not in orderlists:
            orderlists.append("".join(lists[i:j+1])) 
        else:
            continue

anslists=sorted(orderlists)
print(anslists[k-1])

Fixed submission:
s=input()
k=int(input())
uselist=[]
count=0
checker=0
alphabet="abcdefghijklmnopqrstuvwxyz"
while count<=5 and checker<=26:
    for i in alphabet:
        for j in range(len(s)):
            if s[j]==i:
                uselist.append((j,i))
                count+=1
        checker+=1
anslist=[]
for some in uselist:
    count=0
    for j in range(some[0],len(s)):
        anslist.append(s[some[0]:j+1:])
        count+=1
        if count>5:
            break           
anslist=sorted(set(anslist))
print(anslist[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
uselist=[]
count=0
checker=0

alphabet="abcdefghijklmnopqrstuvwxyz"
while count<=5 and checker<=26:
    for i in alphabet:
        for j in range(len(s)):
            if s[j]==i:
                uselist.append((j,i))
                count+=1
        checker+=1
anslist=[]
for some in uselist:
    for j in range(some[0],len(s)):
        anslist.append(s[some[0]:j+1:])
anslist=sorted(set(anslist))
print(anslist[k-1])
    
    


Fixed submission:
s=input()
k=int(input())
uselist=[]
count=0
checker=0
alphabet="abcdefghijklmnopqrstuvwxyz"
while count<=5 and checker<=26:
    for i in alphabet:
        for j in range(len(s)):
            if s[j]==i:
                uselist.append((j,i))
                count+=1
        checker+=1
anslist=[]
for some in uselist:
    count=0
    for j in range(some[0],len(s)):
        anslist.append(s[some[0]:j+1:])
        count+=1
        if count>5:
            break
            
anslist=sorted(set(anslist))

print(anslist[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
uselist=[]
count=0
checker=0

alphabet="abcdefghijklmnopqrstuvwxyz"
while count<=5 and checker<=26:
    for i in alphabet:
        for j in range(len(s)):
            if s[j]==i:
                uselist.append((j,i))
                count+=1
        checker+=1
anslist=[]
for some in uselist:
    for j in range(some[0],len(s)):
        anslist.append(s[some[0]:j+1:])
anslist=sorted(set(anslist))
print(anslist[k-1])
    
    

Fixed submission:
s=input()
k=int(input())
uselist=[]
count=0
checker=0
alphabet="abcdefghijklmnopqrstuvwxyz"
while count<=5 and checker<=26:
    for i in alphabet:
        for j in range(len(s)):
            if s[j]==i:
                uselist.append((j,i))
                count+=1
        checker+=1
anslist=[]
for some in uselist:
    count=0
    for j in range(some[0],len(s)):
        anslist.append(s[some[0]:j+1:])
        count+=1
        if count>5:
            break
            
anslist=sorted(set(anslist))

print(anslist[k-1])
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
data=[[0 for i in range(w+2)] for j in range(h+2)]
for j in range(h):
    s=input()
    for i in range(w):
        if s[i]=="#":
            data[j+1][i+1]=1
flag=True
for i in range(1,h+2):
    for j in range(1,w+2):
        c=0
        for a in range(i-1,i+2):
            for b in range(j-1,j+2):
                c+=data[a][b]
        if c==1:
            flag=False
            break
if flag:
    print("Yes")
else:
    print("No")

Fixed submission:
h,w=map(int,input().split())
data=[[0 for i in range(w+2)] for j in range(h+2)]
for j in range(h):
    s=input()
    for i in range(w):
        if s[i]=="#":
            data[j+1][i+1]=1
flag=True
for i in range(1,h+2):
    for j in range(1,w+2):
        if data[i][j]==1 and data[i-1][j]==data[i+1][j]==data[i][j-1]==data[i][j+1]==0:
            flag=False
            break
if flag:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
lists=[]
for i in range(n):
    s=input()
    lists.append(s)
is_good=[[False for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        p=lists[i][j:]+lists[i][:j]
        flag=True
        for k in range(n):
            if p[k]!=lists[(i+k)%n][j]:
                flag=False
                break
        if flag:
            is_good[i][j]=True

counter=0
for i in range(n):
    for j in range(n):
        flag=True
        for k in range(n):
                if is_good[(i+k)%n][(j+k)%n]==False:
                    flag=False
                    break
        if flag:
            
            counter+=1
print(counter)
            

Fixed submission:
n=int(input())
lists=[]
for i in range(n):
    s=input()
    lists.append(s)
is_good=[[False for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        p=lists[i][j:]+lists[i][:j]
        flag=True
        for k in range(n):
            if p[k]!=lists[(i+k)%n][j]:
                flag=False
                break
        if flag:
            is_good[i][j]=True

counter=0
for i in range(n):
    for j in range(n):
        flag=True
        for k in range(n):
                if is_good[(i+k)%n][(j+k)%n]==False:
                    flag=False
                    break
        if flag:
            
            counter+=1
print(counter)
Buggy python submission (verdict: Runtime Error):
#2d plane 2n points
n=int(input())
cnt=0
red=[]
blue=[]
for _ in range(n):
    x,y=map(int,input().split())
    red.append((x,y))
for _ in range(n):
    x,y=map(int,input().split())
    blue.append((x,y))
red=sorted(red,key=lambda x:x[0])
blue=sorted(blue,key=lambda x:x[0])
blue=blue[::-1]
for i in range(n-1,-1,-1):
    x,y=red[i][0],red[i][1]
    d=[]
    for some in blue:
        X,Y=some[0],some[1]
        if X>x:
            d.append((X,Y))
    if d:
        d=sorted(d,key=lambda x:x[1])
        node=-1
        for some in d:
            if some[1]>y:
                node=some
                cnt+=1
                break
        blue.remove(node)
print(cnt) 

Fixed submission:
#2d plane 2n points
n=int(input())
cnt=0
red=[]
blue=[]
for _ in range(n):
    x,y=map(int,input().split())
    red.append((x,y))
for _ in range(n):
    x,y=map(int,input().split())
    blue.append((x,y))
red=sorted(red,key=lambda x:x[0])
blue=sorted(blue,key=lambda x:x[0])
blue=blue[::-1]
for i in range(n-1,-1,-1):
    x,y=red[i][0],red[i][1]
    d=[]
    for some in blue:
        X,Y=some[0],some[1]
        if X>x:
            d.append((X,Y))
    if d:
        d=sorted(d,key=lambda x:x[1])
        node=0
        for some in d:
            if some[1]>y:
                node=some
                cnt+=1
                break
        if node!=0:
            blue.remove(node)
print(cnt)
Buggy python submission (verdict: Runtime Error):
n=int(input())
lists1=list(map(int,input().split()))
lists2=list(map(int,input().split()))
diff=[]
if n>=2:
    for i in range(n-1):
        diff.append(lists1[i+1]-lists2[i])
    cnt=0
    findlist=[]
    for i in range(n-1):
        cnt=cnt+diff[i]
        findlist.append((cnt,i))
    anslist=sorted(findlist,key=lambda x: x[0])
    base=lists1[0]+sum(lists2)
    print(base2+anslist[-1][0])
elif n==1:
    print(lists1[0]+lists2[0])

Fixed submission:
n=int(input())
lists1=list(map(int,input().split()))
lists2=list(map(int,input().split()))
diff=[0]
if n>=2:
    for i in range(n-1):
        diff.append(lists1[i+1]-lists2[i])
    cnt=0
    findlist=[]
    for i in range(n):
        cnt=cnt+diff[i]
        findlist.append((cnt,i))
    anslist=sorted(findlist,key=lambda x: x[0])
    base=lists1[0]+sum(lists2)
    print(base+anslist[-1][0])
elif n==1:
    print(lists1[0]+lists2[0])
Buggy python submission (verdict: Runtime Error):
#お年玉
n,y=map(int,input().split())
a,b,c=0,0,0
for i in range(2001):
    for j in range(2001):
        if i+j<=n and 10000*i+5000*j+1000*(n-i-j)==y:
            a=i
            b=j
            c=n-i-j
            flag=True
            break
if flag:
  print(a,b,c)
if not flag:
    print(-1,-1,-1)

Fixed submission:
#お年玉
n,y=map(int,input().split())
a,b,c=0,0,0
flag=False
for i in range(2001):
    for j in range(2001):
        if i+j<=n and 10000*i+5000*j+1000*(n-i-j)==y:
            a=i
            b=j
            c=n-i-j
            flag=True
            break
if flag:
  print(a,b,c)
if not flag:
    print(-1,-1,-1)
Buggy python submission (verdict: Runtime Error):
q=int(input())
n =10**3
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
lists=[]
for i in prime:
    lists.append(i)  
lists=sorted(lists) 

checklist=[0]*(10**5+1)
checklist[0]=0
checklist[1]=0
for i in range(2,10**5+1):
    if i%2==0:
        checklist[i]=checklist[i-1]
    elif i%2!=0:
        if (all(i%j!=0 for j in lists) or i in lists) and (all(((i+1)//2)%j!=0 for j in lists) or (i+1)//2 in lists) :
            count+=1
            checklist[i]=checklist[i-1]+1
        else:
            checklist[i]=checklist[i-1]

listss=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    c=checklist[b]-checklist[a-1]
    listss[i]=c
for i in listss:
    print(i)


Fixed submission:
q=int(input())
n =10**3
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
lists=[]
for i in prime:
    lists.append(i)  
lists=sorted(lists) 

checklist=[0]*(10**5+1)
checklist[0]=0
checklist[1]=0
count=0
for i in range(2,10**5+1):
    if i%2==0:
        checklist[i]=checklist[i-1]
    elif i%2!=0:
        if (all(i%j!=0 for j in lists) or i in lists) and (all(((i+1)//2)%j!=0 for j in lists) or (i+1)//2 in lists) :
            count+=1
            checklist[i]=checklist[i-1]+1
        else:
            checklist[i]=checklist[i-1]

listss=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    c=checklist[b]-checklist[a-1]
    listss[i]=c
for i in listss:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
p=int(input())
n = 10**5
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
lists=[]
for i in prime:
    lists.append(i)  
lists=sorted(lists) 
for i in range(p):
    count=0
    a,b=map(int,input().split())
    for j in range(a,b+1):
        if j in prime and (j+1)%2==0 and (j+1)//2 in prime:
            count+=1
    print(count)

Fixed submission:
q=int(input())
n =10**3
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
lists=[]
for i in prime:
    lists.append(i)  
lists=sorted(lists) 

checklist=[0]*(10**5+1)
checklist[0]=0
checklist[1]=0
count=0
for i in range(2,10**5+1):
    if i%2==0:
        checklist[i]=checklist[i-1]
    elif i%2!=0:
        if (all(i%j!=0 for j in lists) or i in lists) and (all(((i+1)//2)%j!=0 for j in lists) or (i+1)//2 in lists) :
            count+=1
            checklist[i]=checklist[i-1]+1
        else:
            checklist[i]=checklist[i-1]

listss=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    c=checklist[b]-checklist[a-1]
    listss[i]=c
for i in listss:
    print(i)