Harryxun/stf_run huggingface dataset:
# coding: utf-8
import sys
inputline = list(input()) #1文字ずつ文字のリストに
akihabara = list("AKIHABARA")

lineLength = len(akihabara) - len(inputline)
# 正解より文字数が多いとき
if lineLength < 0:
    print("NO")
    sys.exit()
# 正解と文字数が同じとき
elif lineLength == 0:
    if inputline == akihabara:
        print("YES")
        sys.exit()
    else:
        print("NO")
        sys.exit()
# 正解より文字数が少ないとき
else:
    count=0
    for i in range(9):
        if i == 8 and len(inputline)<9:
            inputline.append("A")
        elif inputline[i] != akihabara[i]:
            inputline.insert(i, "A")

if inputline == akihabara:
    print("YES")
    sys.exit()
else:
    print("NO")
    sys.exit()


### FIXED CODE ###

# coding: utf-8
import sys
 
inputline = list(input()) #1文字ずつ文字のリストに
akihabara = list("AKIHABARA")

# Aの数
count = 4

lineLength = len(akihabara) - len(inputline)
for i in range( len(inputline) ):
    if inputline[i] == "A":
      count -= 1
#print(count)
# 正解より文字数が多い、あるいは文字数が5文字以下のとき
if lineLength < 0 or len(inputline)+count < 9 :
    print("NO")
# 正解と文字数が同じとき
elif lineLength == 0:
    if inputline == akihabara:
        print("YES")
    else:
        print("NO")
# 正解より文字数が少ないとき

else:
    for i in range(9):
        if i == 8 and len(inputline)<9:
            inputline.append("A")
        elif inputline[i] != akihabara[i]:
            inputline.insert(i, "A")
            
    if inputline == akihabara:
        print("YES")
    else:
        print("NO")
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def main():
    N, M = LI()
    jobsavailable = [[] for _ in range(10**5+1)]
    for _ in range(N):
        a, b = LI()
        if a > M:
            continue
        jobsavailable[M-a].append(b)
    cur_jobs = []
    cnt = 0
    for i in range(1, M+1):
        # a <= iのなかで最大のbがあるものをとりだす
        jobs = jobsavailable[M-i]
        cur_jobs.extend(jobs)
        heapq._heapify_max(cur_jobs)
        if cur_jobs != []:
            j = heapq._heappop_max(cur_jobs)
            cnt += j
    print(cnt)


'''
def main():
    N, M = LI()
    ab = []
    for _ in range(N):
        a, b = LI()
        ab.append((a, b))
    ab = sorted(ab, key=lambda x: (x[1], x[0]))[::-1]
    i = 0
    cnt = 0
    print(ab)
    while 0 < M and i < N:
        day, money = ab[i]
        if day > M:
            pass
        else:
            cnt += money
            M -= 1
        i += 1
    print(cnt)
'''

main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

def main():
    N, M = LI()
    jobsavailable = [[] for _ in range(10**5+1)]
    for _ in range(N):
        a, b = LI()
        if a > M:
            continue
        jobsavailable[M-a].append(b)
    cur_jobs = []
    cnt = 0
    for i in range(1, M+1):
        # a <= iのなかで最大のbがあるものをとりだす
        jobs = jobsavailable[M-i]
        for j in jobs:
            _heappush_max(cur_jobs, j)
        if cur_jobs != []:
            j = _heappop_max(cur_jobs)
            cnt += j
    print(cnt)

main()
import numpy as np
N = int(input())
B = str(input())

B_array = np.array(list(map(int, list(B))))
B_1 = B_array.sum()
mod_list_m1 = []
mod_list = []
mod_list_p1 = []
for i in range(N):
    mod_list.append((2**i) % (B_1))
    mod_list_m1.append((2**i) % (B_1-1))
    mod_list_p1.append((2**i) % (B_1+1))
mod_list = np.array(mod_list)[::-1]
mod_list_m1 = np.array(mod_list_m1)[::-1]
mod_list_p1 = np.array(mod_list_p1)[::-1]

def calc_small(n, iter):
    
    iter += 1
    mod = n % bin(n).count("1")
    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    Z_array = B_array.copy()
    Z_array[i] = 1 if B_array[i] == 0 else 0
    if Z_array.sum() == 0:
        print(1)
        continue
    mod = Z_array.dot(mod_list_p1) % (B_1+1) if B_array[i] == 0 else Z_array.dot(mod_list_m1) % (B_1-1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))
    



### FIXED CODE ###

N = int(input())
B = input()

B_1 = B.count("1")
mod_p1 = int(B,2) % (B_1+1)
if B_1 != 1:
    mod_m1 = int(B,2) % (B_1-1)

def calc_small(n, iter):
    iter += 1
    mod = n % bin(n).count("1")

    if mod == 0:
        return iter
    else:
        return calc_small(mod, iter)

for i in range(N):
    if B_1 == 1 and int(B[i]) == 1:
        print(0)
        continue
    mod = (mod_m1 - pow(2,N-i-1,B_1-1)) % (B_1-1) if int(B[i]) == 1 else (mod_p1 + pow(2,N-i-1,B_1+1)) % (B_1+1)
    iter = 1
    if mod == 0:
        print(iter)
    else:
        print(calc_small(mod, iter))
a=int(input())
b=int(input())
print(max([a+b,a-b,a*b]))

### FIXED CODE ###

a,b=map(int,input().split())
print(max(a+b,a-b,a*b))
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_t(numbers):
    return reduce(math.gcd, numbers)

x=[]
N,X=list(map(int,input().split()))
x=list(map(int,input().split()))
    
gcd_list=[]
for i in range(N):
    gcd_list.append(X-x[i])

print(abs(gcd_t(gcd_list)))

### FIXED CODE ###

def gcd(m,n):   
    if(n==0):    return m
    else:    return gcd(n,m%n)

x=[]
N,X=list(map(int,input().split()))
x=list(map(int,input().split()))
    
ans=abs(X-x[0])
for i in range(N):
    ans=gcd(ans,abs(x[i]-X))

print(ans)
a = int(input())
b = 1
while True:
	if b < a+1:
		x = map(int,input().split(' '))
		x.sort()
		if a*2 + b*2 = c*2:
			print('YES')
		else:
			print('NO')
		b += 1
		continue
	else:
		break

### FIXED CODE ###

for val in range(input()):
	x = map(int,raw_input().split(' '))
	x.sort()
	if x[0]**2+x[1]**2==x[2]**2: print 'YES'
	else: print 'NO'
N = int(input())
arr = []
for i in range(N):
  arr.append(int(input()))
for i range(N):
  cop = arr.copy()
  del cop[i]
  print(max(cop))

### FIXED CODE ###

N = int(input())
arr = []
for i in range(N):
  arr.append(int(input()))
max_inds = []
max_v = arr[0]
for i in range(N):
  if arr[i] > max_v:
    max_v = arr[i]
for i in range(N):
  if arr[i] == max_v:
    max_inds.append(i)
for i in range(N):
  if len(max_inds) >= 2:
    print(max_v)
  else:
    if i == max_inds[0]:
      cop = arr.copy()
      del cop[i]
      print(max(cop))
    else:
      print(max_v)
n=input()
a=list(map(int,input().split()))
for i in a:
    if i%2==0:
        if i%3==0 or i%5==0:
            result='APPROVED'
        else:
            result='DENIED'
            break
print(result)

### FIXED CODE ###

n=input()
a=list(map(int,input().split()))
for i in a:
    if i%2==0:
        if i%3==0 or i%5==0:
            pass
        else:
            print('DENIED')
            exit(0)
print('APPROVED')
input_line = input().split(" ")
X = int(input_line[0])
Y = int(input_line[1])
Pat = 0
for i in range(X + 1):
  	C = i
	T = X - i
    Cf = C * 2
    Tf = T * 4
    F = Cf + Tf
	if Y == F:
      Pat = Pat + 1
if Pat >= 0:
  print("Yes")
else:
  print("No")
   
  
  
  


### FIXED CODE ###

input_line = input().split(" ")
X = int(input_line[0])
Y = int(input_line[1])
Pat = 0
for i in range(X + 1):
  C = i
  T = X - i
  Cf = C * 2
  Tf = T * 4
  F = Cf + Tf
  if Y == F:
      Pat = Pat + 1
if Pat > 0:
  print("Yes")
else:
  print("No")
n = int(input())
h= list(map(int,input().split()))
a = []
cnt = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        cnt = cnt + 1
    else:
        cnt = 0
    a.append(cnt)
print(max(a))

### FIXED CODE ###

n = int(input())
h= list(map(int,input().split()))
a = [0]
cnt = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        cnt = cnt + 1
    else:
        cnt = 0
    a.append(cnt)
print(max(a))
if len(S)==2:
    print(S)
elif len(S)==3:
    print(S[::-1])

### FIXED CODE ###

S=input()
if len(S)==2:
    print(S)
elif len(S)==3:
    print(S[::-1])
a = int(input())
b = int(input())

print((a-1)*(b-1))

### FIXED CODE ###

a, b = [int(i) for i in input().split()]

print((a-1)*(b-1))
N = int(input())
R=[["1","2","3","4","5","6","7","8","9"]]
count=9
for i in range(N):
  if count>=N:
    break
  else:
    temp=[]
    for r in R[i]:
      if r[-1]=="9":
        temp.append(str(r)+str(int(r[-1])-1))
        temp.append(str(r)+str(int(r[-1])))
      elif r[-1]=="0":
        temp.append(str(r)+str(int(r[-1])))
        temp.append(str(r)+str(int(r[-1])+1))
      else:
        temp.append(str(r)+str(int(r[-1])-1))
        temp.append(str(r)+str(int(r[-1])))
        temp.append(str(r)+str(int(r[-1])+1))
    R.append(temp)
    count+=len(temp)
N=N-(count-len(temp))
print(R[-1][N-1])

### FIXED CODE ###

N = int(input())
R=[["1","2","3","4","5","6","7","8","9"]]
count=9
temp=[]
for i in range(N):
  if count>=N:
    break
  else:
    temp=[]
    for r in R[i]:
      if r[-1]=="9":
        temp.append(str(r)+str(int(r[-1])-1))
        temp.append(str(r)+str(int(r[-1])))
      elif r[-1]=="0":
        temp.append(str(r)+str(int(r[-1])))
        temp.append(str(r)+str(int(r[-1])+1))
      else:
        temp.append(str(r)+str(int(r[-1])-1))
        temp.append(str(r)+str(int(r[-1])))
        temp.append(str(r)+str(int(r[-1])+1))
    R.append(temp)
    count+=len(temp)
N=N-(count-len(temp))
print(R[-1][N-1])
N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
def_Bsum = sum(B)
 
for i in range(N+1):
    if(i==0):
        if (A[i] < B[i]):
            B[i] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i]$　　　　　　　　#倒せたら０にする。最後引いた時に残るように。
            B[i] = 0
 
    if(0<i<N):
        if(A[i] < B[i-1]):
            B[i-1] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i-1]
            B[i-1] = 0
 
            if (A[i] < B[i]):
                B[i] -= A[i]
                A[i] = 0
            else:
                A[i] -= B[i]
                B[i] = 0
 
    if(i==N):
        if (A[i] < B[i-1]):
            B[i-1] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i-1]
            B[i-1] = 0
 
 
ans = def_Bsum - sum(B)

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
def_Bsum = sum(B)
 
for i in range(N+1):
    if(i==0):                  #倒せたら０にする。最後に引いたら残るように
        if (A[i] < B[i]):
            B[i] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i]
            B[i] = 0
 
    if(0<i<N):
        if(A[i] < B[i-1]):
            B[i-1] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i-1]
            B[i-1] = 0
 
            if (A[i] < B[i]):
                B[i] -= A[i]
                A[i] = 0
            else:
                A[i] -= B[i]
                B[i] = 0
 
    if(i==N):
        if (A[i] < B[i-1]):
            B[i-1] -= A[i]
            A[i] = 0
        else:
            A[i] -= B[i-1]
            B[i-1] = 0
 
 
ans = def_Bsum - sum(B)

print(ans)
from math import gcd
a,b = map(int, input().split())
#print((a*b)//gcd(a,b))


### FIXED CODE ###

from fractions import gcd
a,b = map(int, input().split())
print((a*b)//gcd(a,b))
x,y,z = map(int,input().split())

if(x=5):
  if(y=5):
    if(z=7):
      print("YES")
    else:
      print("NO")
  elif(y=7):
    if(z=5):
      print("YES")
    else:
      print("NO")
elif(x=7):
  if(y=5):
    if(z=5):
      print("YES")
    else:
      print("NO")
else:
  print("NO")
    

### FIXED CODE ###

x,y,z = map(int,input().split())
 
if(x==5):
  if(y==5):
    if(z==7):
      print("YES")
    else:
      print("NO")
  elif(y==7):
    if(z==5):
      print("YES")
    else:
      print("NO")
elif(x==7):
  if(y==5):
    if(z==5):
      print("YES")
    else:
      print("NO")
  else:
    print("NO")
else:
  print("NO")
from scipy.special import comb
n,m = map(int,input().split())
ans1=0
ans2=0
if n > 1:
    ans1=comb(n,2,exact=True)
if m > 1:
    ans2=comb(m,2,exact=True)
print(ans1+ans2)

### FIXED CODE ###

import math
def comb(x,y):
    return math.factorial(x)//(math.factorial(x-y)*math.factorial(y))
n,m = map(int,input().split())

ans1=0
ans2=0
if n > 1:
    ans1=comb(n,2)
if m > 1:
    ans2=comb(m,2)
print(ans1+ans2)
n = int(input())
print(n**2 - int(input())

### FIXED CODE ###

n = int(input())
print(n**2 - int(input()))
round = 3.1415

r = input()
print(r*2*rount)

### FIXED CODE ###

round = 6.28318530717958623200

 
r = int(input())
print(r*round)
def main():
    N=int(input())
    P=[0]*N
    p=[False]*(N+1)
    P[0]=int(input())
    for i in range(N-1):
        P[i+1=int(input())
        if P[-1]-1 in P[:-1]:
            p[P[-1]-1] = True
    ans=0
    j=0
    for i in range(N):
        if p[i]==True:
            j+=1
        else:
            ans=max(ans,j)
            j=0
    print(N-ans-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N=int(input())
    p=[False]*(N+1)
    c=[False]*(N+1)
    for i in range(N):
        x=int(input())
        c[x]=True
        if c[x-1]:
            p[x-1] = True
    ans=0
    j=0
    for i in range(1,N+1):
        if p[i]:
            j+=1
        else:
            ans=max(ans,j)
            j=0
    ans=max(ans,j)
    print(N-ans-1)

if __name__ == "__main__":
    main()
import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

mod = 1000000007
N=int(2*1e5+100)
sz = [0]*N
dp = [0]*N
gr = defaultdict(list)
def modPow(a,b):
    ans=1
    while (b):
        if (b&1): ans=(ans*a)%mod
        b>>=1
        a=(a*a)%mod
    return ans

def modInv(x):
    return modPow(x,mod-2)

def dfs(x, par):
    sz[x]=1
    for item in gr[x]:
        if item==par: continue
        dfs(item,x)
        sz[x]+=sz[item]

def dfs1(x, par):
    for item in gr[x]:
        if item==par: continue
        dp[item]=(dp[x]*(n-sz[item]))%mod
        dp[item]=(dp[item]*modInv(sz[item]))%mod
        dfs1(item,x)

n = int(input())
for i in range(n-1):
    x,y = mapi()
    gr[x].append(y)
    gr[y].append(x)
dfs(1,0)
dp[1]=1
for i in range(1,n+1):
    dp[1]=(dp[1]*sz[i])%mod
dfs1(1,0)
res = 1
for i in range(1,n+1):
    res = (res*i)%mod
for i in range(1,n+1):
    dp[i]=(res*modInv(dp[i]))%mod
for i in range(1,n+1):
    print(dp[i])


### FIXED CODE ###

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------
sys.setrecursionlimit(100005)
mod = 1000000007
N=int(2*1e5+100)
sz = [0]*N
dp = [0]*N
gr = defaultdict(list)
def modPow(a,b):
    ans=1
    while (b):
        if (b&1): ans=(ans*a)%mod
        b>>=1
        a=(a*a)%mod
    return ans

def modInv(x):
    return modPow(x,mod-2)

def dfs(x, par):
    sz[x]=1
    for item in gr[x]:
        if item==par: continue
        dfs(item,x)
        sz[x]+=sz[item]

def dfs1(x, par):
    for item in gr[x]:
        if item==par: continue
        dp[item]=(dp[x]*(n-sz[item]))%mod
        dp[item]=(dp[item]*modInv(sz[item]))%mod
        dfs1(item,x)

n = int(input())
for i in range(n-1):
    x,y = mapi()
    gr[x].append(y)
    gr[y].append(x)
dfs(1,0)
dp[1]=1
for i in range(1,n+1):
    dp[1]=(dp[1]*sz[i])%mod
dfs1(1,0)
res = 1
for i in range(1,n+1):
    res = (res*i)%mod
for i in range(1,n+1):
    dp[i]=(res*modInv(dp[i]))%mod
for i in range(1,n+1):
    print(dp[i])
A,B = map(int,input().split())
ans = int((A*B) // 1)
print(ans)

### FIXED CODE ###

# Multiplication 3
A, B = input().split()
A = int(A)
B = int(B.replace('.', ''))
ans = (A*B) // 100
print(ans)
S,T = map(str, input().sprit())
if T.startswith(S):
  print("Yes")
else:
  print("No")


### FIXED CODE ###

S = str(input())
T = str(input())

if T.startswith(S):
  print("Yes")
else:
  print("No")
N = int(input())
A = list(map(int, input().strip().split()))
X = []
X = X.append(sum(A[0::2])-sum(A[1::2]))
for k in range (N-1):
  X = X.extend(2*A[k] - X[k])
print(X)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().strip().split()))
X = []
X.append(sum(A[0::2])-sum(A[1::2]))
for k in range (N-1):
  X.append(2*A[k] - X[k])
print(*X, sep=" ")
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import collections

N, M, P = rl()
E = []
edges = collections.defaultdict(list)
redges = collections.defaultdict(list)
for i in range(M):
	a, b, c = rl()
	E.append((a-1, b-1, P-c))
	edges[a-1].append(b-1)
	redges[b-1].append(a-1)

visited = {}
def dfs(n):
	if n in visited: return
	visited[n] = 1
	for e in edges[n]:
		dfs(e)
rvisited = {}
def rdfs(n):
	if n in rvisited: return
	rvisited[n] = 1
	for e in redges[n]:
		rdfs(e)

dfs(0)
rdfs(N-1)
ok = [False] * N
for n in range(N):
	if n in visited and n in rvisited:
		ok[n] = True
V = list(range(N))

def belmanford(V, E, s=0):
	D = [float('inf')] * len(V)
	D[s] = 0
	P = [None] * len(V)
	update = True
	step = 0
	while update:
		update = False
		for u, v, c in E:
			if not ok[u]: continue
			if not ok[v]: continue
			if D[v] > D[u] + c:
				D[v] = D[u] + c
				P[v] = (u, c)
				update = True
		step += 1
		if step > N:
			return None, None
	return D, P

D, P = belmanford(V, E)
if D == None:
	print(-1)
else:
	print(max(-D[N-1], 0))


### FIXED CODE ###

import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

import sys
sys.setrecursionlimit(1000000)

import collections

N, M, P = rl()
E = []
edges = collections.defaultdict(list)
redges = collections.defaultdict(list)
for i in range(M):
	a, b, c = rl()
	E.append((a-1, b-1, P-c))
	edges[a-1].append(b-1)
	redges[b-1].append(a-1)

visited = {}
def dfs(n):
	if n in visited: return
	visited[n] = 1
	for e in edges[n]:
		dfs(e)
rvisited = {}
def rdfs(n):
	if n in rvisited: return
	rvisited[n] = 1
	for e in redges[n]:
		rdfs(e)

dfs(0)
rdfs(N-1)
ok = [False] * N
for n in range(N):
	if n in visited and n in rvisited:
		ok[n] = True
V = list(range(N))

def belmanford(V, E, s=0):
	D = [float('inf')] * len(V)
	D[s] = 0
	P = [None] * len(V)
	update = True
	step = 0
	while update:
		update = False
		for u, v, c in E:
			if not ok[u]: continue
			if not ok[v]: continue
			if D[v] > D[u] + c:
				D[v] = D[u] + c
				P[v] = (u, c)
				update = True
		step += 1
		if step > N:
			return None, None
	return D, P

D, P = belmanford(V, E)
if D == None:
	print(-1)
else:
	print(max(-D[N-1], 0))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
 
 
def main():
    num = int(stdin.readline())
 
    M = []
    for _ in xrange(num):
        M.append([int(s) for s in stdin.readline().split()])
 
    g = set(xrange(1, num+1))
    index = g.pop()
    h = {index}
    weight = 0
 
    while g:
        minimum = maxint
        for j in h:
            mj = M[j-1]
            for i in g:
                if 0 <= mj[i-1] < minimum:
                    index = i
                    minimum = mj[i-1]
        h.add(index)
        g.remove(index)
        weight += minimum
 
    print(weight)
 
 

### FIXED CODE ###

import sys
     
global status, d
status = {}
d=0
 
def mst(p1, GRAPH):
    global status
     
    edge={}
    total = 0
    mini = 0
    while True:
        status[p1]=True
        for p2 in range(len(status)):
            if status[p2]==False and GRAPH.has_key((p1,p2)):
                edge[(p1, p2)]=GRAPH[(p1, p2)]
        mini=1000000
        for key, value in edge.items():
            if status[key[1]]==True:
                del edge[key]
                continue
            if value <mini:
                key0 = key
                mini = value
        if mini!=1000000:
            total+=mini
            p1=key0[1]
        else:
            break
     
    return total
 
n = int(raw_input())
x = {}
for i in range(n):
    seq = map(int,raw_input().split())
    for j in range(n):
        tmp = seq[j]
        if tmp != -1:
            x[(i, j)]=tmp
    status[i] = False
 
print mst(0, x)
x,y=map(int,input().split())
a=(2*x-y)/3
b=(-x+2*y)/3
if (2*x-y)%3!=0:
    print(0)
    exit()
a=int(a)
b=int(b)
if a<0 or b<0:
  print(0):
    exit()
mod=10**9+7
if a==0 or b==0:
  print((a+b)%mod)
  exit()
def comb(x,y):
    s=x
    t=1
    for i  in range(1,y):
        s=(s*(x-i))%mod
    for j  in range(1,y+1):
        t=(t*j)%mod
    return (s*pow(t,mod-2,mod))%mod
print(comb(a+b,min(a,b)))

### FIXED CODE ###

x,y=map(int,input().split())
if (2*x-y)%3!=0 or (x-2*y)%3!=0:
  print(0)
  exit()
a=(2*x-y)//3
b=(2*y-x)//3
if a<0 or b<0:
  print(0)
  exit()
mod=10**9+7
def comb(x,y):
    s=1
    t=1
    for i in range(1,y+1):
        s=s*(x-i+1)%mod
        t=t*(i)%mod
    return (s*pow(t,mod-2,mod))%mod
print(comb(a+b,min(a,b)))
#　n以下の整数の素数列挙（エラトステネスの篩）
#-------------------------------------------------------------------------
import numpy as np

def eratosthenes(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
#-------------------------------------------------------------------------
from itertools import accumulate

N = int(input())
L = [0] * N
R = [0] * N
A = eratosthenes(10*5)
B = [0] * 10*5
C = [0] * N

for i in range(10*5):
    if i in A:
        if (i+1)/2 in A:
            B[i] = 1

C = [0] + list(accumulate(B)) #out of rangeの回避

for i in range(N):
    L[i], R[i] = map(int, input().split())
for i in range(N):
    print(C[R[i]+1]-C[L[i]])

### FIXED CODE ###

from itertools import accumulate
# エラトステネスの篩
# is_prime := 1~nが素数か否か
# table := 2~nのうち素数
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

max_R = max(R)
is_prime, table = sieve(max_R)

check = [0]*(max_R + 1)
for i in range(0, max_R + 1):
    if (i % 2 == 1):
        if (is_prime[i-1] and is_prime[(i+1)//2-1]):
            check[i] = 1

# 累積和
check = [0] + check
check = list(accumulate(check))

for i in range(Q):
    print(check[R[i] + 1] - check[L[i]])