Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N=int(input())
l=[]
for i in range(N):
  l.append(int(input()))
for i in range(N):
  if i==0:
    l1=l[1:]
  elif i==N:
    l1=l[:N]
  else:
    l1=l[:i]+l[i+1:]
  print(max(l1))

### FIXED CODE ###

N=int(input())
l=[]
for i in range(N):
  l.append(int(input()))
l_max=max(l)
i=l.index(l_max)
if i==0:
  l1=l[1:]
  print(max(l1))
  for a in range(N-1):
    print(l_max)
elif i==N:
  l1=l[:N]
  for a in range(N-1):
    print(l_max)
  print(max(l1))
else:
  l1=l[:i]+l[i+1:]
  for a in range(i):
    print(l_max)
  print(max(l1))
  for a in range(N-i-1):
    print(l_max)
### BUGGY CODE ###

def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


n,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
print(knap(n,W,w,v))

### FIXED CODE ###

def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


n,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
print(knap(n,W,w,v))
### BUGGY CODE ###

l=sorted(map(int,input().split()))
cnt=0
while l[2]-l[1]>1 or l[2]-l[0]>1:
    print(0)
    if l[2]-1>l[0]: l[1]+=2
    else: l[1]+=2
    cnt+=1
if l[0]==l[1]==l[2]: print(cnt)
elif l[1]==l[0]:print(cnt+1)
else:print(cnt+2)

### FIXED CODE ###

l=sorted(map(int,input().split()))
cnt=0
while l[2]-l[1]>1 or l[2]-l[0]>1:
    if l[2]-1>l[0]: l[0]+=2
    else: l[1]+=2
    cnt+=1
if l[0]==l[1]==l[2]: print(cnt)
elif l[1]==l[0]:print(cnt+1)
else:print(cnt+2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main():
    # 入力
    st = input()

    # if len(st) < 4:
    #     print(0)
    #     return

    # 右からi文字目から最後の数字までを数値化したものについてmodを計算していく
    mod_res_dic = {0: [0]}
    tmp_mod_val = 0
    r_st = ''.join(list(reversed(st)))
    for i in range(1, len(r_st) + 1):
        target_st = r_st[i-1:i]
        mod_res = ((10 ** (i-1)) * int(target_st) + tmp_mod_val) % 2019
        ls = mod_res_dic.setdefault(mod_res, [])
        ls.append(i)
        tmp_mod_val = mod_res

    # print(mod_res_dic)
    # modが同じペアのものについて、iからj文字目までを2019で割り切れるので、その組み合わせを計算
    cnt = 0
    for v in mod_res_dic.values():
        comb = len(v)
        if comb < 2:
            continue
        cnt += (comb * (comb - 1)) / 2

    print(int(cnt))


main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():
    # 入力
    st = input()

    # if len(st) < 4:
    #     print(0)
    #     return

    # 右からi文字目から最後の数字までを数値化したものについてmodを計算していく
    mod_res_dic = {0: [0]}
    tmp_mod_val = 0
    r_st = ''.join(list(reversed(st)))
    cnt = 0
    for i in range(len(r_st)):
        target_st = r_st[i:i+1]
        # mod_res = ((10 ** i) * int(target_st) + tmp_mod_val) % 2019
        tmp_mod_val += int(target_st)*pow(10, i, 2019)
        tmp_mod_val %= 2019
        ls = mod_res_dic.setdefault(tmp_mod_val, [])
        ls.append(i-1)
        if len(ls) > 1:
            cnt += len(ls)-1
        # tmp_mod_val = mod_res

    # print(mod_res_dic)
    # modが同じペアのものについて、iからj文字目までを2019で割り切れるので、その組み合わせを計算
    # cnt = 0
    # for v in mod_res_dic.values():
    #     comb = len(v)
    #     if comb < 2:
    #         continue
    #     cnt += (comb * (comb - 1)) / 2

    print(int(cnt))


main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline()
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
ans = []
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      ans.append(-1)
    else:
      ans.append(hq[0])
print(*ans,sep="\n")




### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
import numpy as np
H, W = list(map(int, input().split()))
L = np.asarray([True if j == "#" else False for i in range(H) for j in input()])
all_count = H * W
blacks = np.where(L)[0]
#print(blacks)
black_count = len(blacks)

cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  L[blacks] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect
N=int(input())
X=[int(i) for i in input().split()]
L=int(input())
Q=int(input())
#T=[[int(i) for i in input().split()] for i in range(Q)]
T=[]
for i in range(Q):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    T.append((a-1,b-1))
F=[0]*N
for i in range(N):
    F[i]= bisect(X, X[i] + L) -1
for a,b in T:
    k=F[a]
    num=1
    while k<b:
        num+=1
        k=F[k]
    print(num)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect
N=int(input())
X=[int(i) for i in input().split()]
L=int(input())
Q=int(input())
#T=[[int(i) for i in input().split()] for i in range(Q)]
T=[]
for i in range(Q):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    T.append((a-1,b-1))
F=[0]*N
for i in range(N):
    F[i]= bisect(X, X[i] + L) -1
#print(F)
dp=[ [N-1] * (N) for i in range(18)]

for i in range(N):
    #dp[0][i]=i
    dp[0][i]=F[i]
for c in range(1,18):
    for i in range(N):
        dp[c][i] = dp[c-1][ dp[c-1][i] ]
#print(dp)

def f(a,b):
    num=0
    t = a
    while True:
        for i in range(18):
            if dp[i][t]>=b:
                s=i
                break
        if s==0:
            num+=1
            break
        num += pow(2, s - 1)
        t = dp[s-1][t]
    print(num)
for a,b in T:
    f(a,b)
### BUGGY CODE ###

def solve(h,w,ch,cw,dh,hw,s):
    d=[[1,0],[-1,0],[0,1],[0,-1]]
    INF=10**12
    path=[[INF]*w for _ in range(h)]
    ans=0
    st=[]
    st=deque()
    st.append((ch,cw,0))
    wp=[]
    wp=deque()
    while st:
      nx,ny,ncost=st.popleft()
      wp.append((nx,ny,ncost))
      path[nx][ny]=ncost
      for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if (0<=x<=h-1) and (0<=y<=w-1):
          if s[x][y]!='#' and path[x][y]>ncost:
            path[x][y]=ncost
            st.append((x,y,ncost))
      if len(st)==0:
        while wp:
          nx,ny,ncost=wp.popleft()
          for i in range(-2,3):
            for j in range(-2,3):
              if (i,j)==(0,0) or (i,j)==(1,0) or (i,j)==(0,1) or (i,j)==(-1,0) or (i,j)==(0,-1):
                continue
              x,y=i+nx,j+ny
              if (0<=x<=h-1) and (0<=y<=w-1):
                if s[x][y]!='#' and path[x][y]>ncost+1:
                  path[x][y]=ncost+1
                  st.append((x,y,ncost+1))
    if path[dh][dw]==INF:
      print(-1)
    else:
      print(path[dh][dw])

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    from collections import deque
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    solve(h,w,ch,cw,dh,dw,s)

### FIXED CODE ###

def solve(h,w,ch,cw,dh,hw,s):
    d=[[1,0],[-1,0],[0,1],[0,-1]]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + d]
    INF=10**12
    path=[[INF]*w for _ in range(h)]
    ans=0
    st=[]
    st=deque()
    st.append((ch,cw,0))
    wp=[]
    wp=deque()
    while st:
      nx,ny,ncost=st.popleft()
      wp.append((nx,ny,ncost))
      path[nx][ny]=ncost
      for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if (0<=x<=h-1) and (0<=y<=w-1):
          if s[x][y]!='#' and path[x][y]>ncost:
            path[x][y]=ncost
            st.append((x,y,ncost))
      if len(st)==0:
        while wp:
          nx,ny,ncost=wp.popleft()
          for dx,dy in warp:
              x,y=nx+dx,ny+dy
              if (0<=x<=h-1) and (0<=y<=w-1):
                if s[x][y]!='#' and path[x][y]>ncost+1:
                  path[x][y]=ncost+1
                  st.append((x,y,ncost+1))
    if path[dh][dw]==INF:
      print(-1)
    else:
      print(path[dh][dw])

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    from collections import deque
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    solve(h,w,ch,cw,dh,dw,s)
### BUGGY CODE ###

N = int(input())
r = [None]*N
s = 0

same = []
other = []

for _ in range(N-1):
    u, v, w = [int(c) for c in input().split()]
    u -= 1
    v -= 1

    if w%2==0:
        if   r[u] != None and r[v] == None:
            r[v] = r[u]
        elif r[u] == None and r[v] != None:
            r[u] = r[v]
        elif r[u] == None and r[v] == None:
            r[u] = r[v] = s
            s+=1
        else:
            same.append((r[u],r[v]))
            
    if w%2==1:
        if r[u] == None:
            r[u] = s
            s+=1
        if r[v] == None:
            r[v] = s
            s+=1
        other.append((r[u],r[v]))
        
color = [{r[0]},set()]

while len(color[0])+len(color[1]) < s:
    for k1, k2 in same:
        for cl in color:
            if k1 in cl: cl.add(k2)
            if k2 in cl: cl.add(k1)

    for k1, k2 in other:
        for cl1, cl2 in ((color[0],color[1]), (color[1],color[0])):
            if k1 in cl1: cl2.add(k2)
            if k2 in cl1: cl2.add(k1)

cmap = [0]*s
for cc in color[1]:
    cmap[cc]=1

for rr in r:
    print(cmap[rr])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())
d = {}
e = [[] for _ in range(N)]
dd = [-1]*N
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    e[u-1].append(v-1)
    e[v-1].append(u-1)
    d[(u-1,v-1)]= d[(v-1,u-1)] = w

def dfs(i, _d):
    dd[i] = _d
    for c in e[i]:
        if dd[c]!=-1: continue
        dfs(c, _d+d[(i,c)])

dfs(0,0)
for _dd in dd:
    print(_dd%2)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
I = 0
J = 0
K = 0
for i in range(N):
    if a[i] == 1:
        I += 1
    if a[i] == 2:
        J += 1
    if a[i] == 3:
        K += 1

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
for k in range(K+1):
    for j in range(J+K+1):
        if j+k > N:
            break
        for i in range(N+1):
            S = i+j+k
            if S > N:
                break
            if S == 0:
                continue
            dp[i][j][k] = (i*dp[i-1][j][k]+j*dp[i+1][j-1][k]+k*dp[i][j+1][k-1]+N)/S
print(dp[I][J][K])

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
I = 0
J = 0
K = 0
for i in range(N):
    if a[i] == 1:
        I += 1
    if a[i] == 2:
        J += 1
    if a[i] == 3:
        K += 1

dp = [[[0.0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
for k in range(K+1):
    for j in range(J+K+1):
        if j+k > N:
            break
        for i in range(N+1):
            S = i+j+k
            if S > N:
                break
            if S == 0:
                continue
            dp[i][j][k] = (i*dp[i-1][j][k]+j*dp[i+1][j-1][k]+k*dp[i][j+1][k-1]+N)/S
print(dp[I][J][K])
### BUGGY CODE ###

def move(S, v):
    next = [0 for _ in range(len(S))]
    for i in range(len(S)):
        if S[i] == 'R':
            next[i + 1] += v[i]
        else:
            next[i - 1] += v[i]
    return next
S = input()

V = [1 for _ in range(len(S))]
Vi = move(S,V)
count = 1
while(True):
    next = move(S, Vi)
    count += 1
    if next == V:
        if count %2 == 1:
            result = Vi
        else:
            result = V
        print(' '.join([str(i) for i in result]))
        break
    Vi, V = next, Vi


### FIXED CODE ###

S = input()
N = len(S)
V = [0 for _ in range(len(S))]
Vi = V[:]
def move(S, v):
    next = [0 for _ in range(len(S))]
    for i in range(len(S)):
        if S[i] == 'R':
            next[i + 1] += v[i]
        else:
            next[i - 1] += v[i]
    return next

nearestL = V[:]
nearestR = V[:]
lastL = N - 1
lastR = 0

for i in range(N - 1, -1, -1):
    if S[i] == 'L':
        lastL = i
    else:
        nearestL[i] = lastL
for i in range(N):
    if S[i] == 'R':
        lastR = i
    else:
        nearestR[i] = lastR

count = 0

maxTurn = 0
for i in range(N):
    if S[i] == 'R':
        dist = abs(i - nearestL[i])
        vec = V if dist % 2 == 0 else Vi
        vec[nearestL[i]] += 1
        maxTurn = max(maxTurn, dist)
    else:
        dist = abs(i - nearestR[i])
        vec = V if dist % 2 == 0 else Vi
        vec[nearestR[i]] += 1
        maxTurn = max(maxTurn, dist)
# print(maxTurn)
# print(' '.join(S))
# print(' '.join([str(i) for i in V]))
# print(' '.join([str(i) for i in Vi]))

Vi = move(S, Vi)
for i in range(N):
    V[i] += Vi[i]

# if (maxTurn % 2 == 1):
#     V = move(S, V)
print(' '.join([str(i) for i in V]))
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
l = int(((N**2)+1)/2)
b = []
for i in range(l):
    b.append(1)
    b.append(-1)
b = np.array(b)
# print(b)
c = (np.delete(b, 2*l-1, axis=None)).reshape(N,N)
# print(c)
d = c.reshape(N,N)
inv = 0.5*( np.triu(c) - ( np.tril(c) - np.eye(N) ) )
g = np.eye(N)
x = 2*(np.dot(inv,a))
ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
a = np.array(A)
# l = int(((N*N)+1)/2)
b = []
for i in range(N):
    if i%2==0:
        b.append(1)
    else:
        b.append(-1)
c = np.dot(np.array(b),a)
x = [c]
for j in range(1,N):
    x_j = 2*a[j-1] - x[j-1]
    x.append(x_j)
ans = list(map(str, list(map(int, list(x)))))
print(" ".join(ans))
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = str(input())

dic = defaultdict(int)

for i in range(2 ** N):
    a = str()
    b = str()
    for j in range(N):
        if (i >> j) & 1:
            a += S[j + N]
        else:
            b += S[j + N]
    
    dic[(a, b)] += 1

count = 0
for i in range(2 ** N):
    a = str()
    b = str()
    for j in range(N):
        if (i >> j) & 1:
            a += S[j]
        else:
            b += S[j]
    count += dic[b[::-1], a[::-1]]

print (count)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = str(input())

dic = defaultdict(int)

for i in range(2 ** N):
    a = str()
    b = str()
    for j in range(N):
        if (i >> j) & 1:
            a += S[j + N]
        else:
            b += S[j + N]
    
    dic[(a, b)] += 1

count = 0
for i in range(2 ** N):
    a = str()
    b = str()
    for j in range(N):
        if (i >> j) & 1:
            a += S[j]
        else:
            b += S[j]
    count += dic[b[::-1], a[::-1]]

print (count)
### BUGGY CODE ###

def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
        t.sort(reverse=True) 
print(m)

### FIXED CODE ###

def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
print(m)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    N, M, P = map(int, input().split())
    edge = [[] for _ in range(N)]
    g = [[] for _ in range(N)]
    rg = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge[A].append((B,C))
        g[A].append(B)
        rg[B].append(A)

    # 0 => N-1の間にある閉路を検出したいので
    # 0とN-1からたどりつけない場所は前処理で取り除く
    visited = [False] * N
    rvisited = [False] * N
    Q = deque()
    Q.append(0)
    while Q:
        v = Q.popleft()
        visited[v] = True
        for i in g[v]:
            if not visited[i]:
                Q.append(i)

    Q.append(N-1)
    while Q:
        v = Q.popleft()
        rvisited[v] = True
        for i in rg[v]:
            if not rvisited[i]:
                Q.append(i)
    
    OK = [False] * N
    for i in range(N):
        OK[i] = visited[i] & rvisited[i]
    
    new_edge = []
    for s in range(N):
        for t, c in edge[s]:
            if OK[s]:
                new_edge.append((s,t,c))

    flag = True
    d = [float('inf')] * N
    d[0] = 0
    step = 0
    while flag:
        flag = False
        for A, B, C in new_edge:
            newD = d[A] + C
            if newD < d[B]:
                d[B] = newD
                flag = True
        step += 1
        if step > N:
            print(-1)
            exit()

    print(max(0,-d[N-1]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M, P = map(int, input().split())
    edge = [[] for _ in range(N)]
    redge = [[] for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        C -= P
        C = -C
        edge[A].append((B,C))
        redge[B].append(A)

    # 0 => N-1の間にある閉路を検出したいので
    # 0とN-1からたどりつけない場所は前処理で取り除く
    
    visited1, visited2 = {0}, {N-1}
    
    stack = [0]
    while stack:
        v = stack.pop()
        for dest, _ in edge[v]:
            if dest in visited1:
                continue
            visited1.add(dest)
            stack.append(dest)
    
    stack = [N-1]
    while stack:
        v = stack.pop()
        for dest in redge[v]:
            if dest in visited2:
                continue
            visited2.add(dest)
            stack.append(dest)
    
    OK = visited1 & visited2
    
    new_edge = [[] for _ in range(N)]
    for s in range(N):
        for t, c in edge[s]:
            if t in OK:
                new_edge[s].append((t,c))

    flag = True
    d = [float('inf')] * N
    d[0] = 0
    #ベルマンフォード法、N回実行してまだ更新されている場合は負の閉路が存在する
    for _ in range(N):
        flag = False
        for v, e in enumerate(new_edge):
            for t, c in e:
                if d[v] != float('inf') and d[v] + c < d[t]:
                    d[t] = d[v] + c
                    flag = True
        if not flag:
            print(max(0,-d[N-1]))
            exit()
    else:
        print(-1)
        exit()


if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):
        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

def main():
    N,M = map(int,input().split())
    e = [[] for i in range(N)]
    t = 0
    a = []
    for i in range(M):
        r,l,d = map(int,input().split())
        e[r-1].append([l-1,d])
        e[l-1].append([r-1,-d])
        a.append(r-1)
        a.append(l-1)
        t = r-1

    col = [ float("inf") for i in range(N) ]
    def dfs(i,c):

        for node in e[i]:
            if col[node[0]] == float("inf"):
                col[node[0]] = c + node[1]
                dfs(node[0],c+node[1])
            elif col[node[0]] != c + node[1]:
                print("No")
                exit()


    dfs(t,0)
    a = list(set(a))
    for i in a:
        if col[i] == float("inf"):
            dfs(i,0)


    print("Yes")


if __name__ == '__main__':
    main()
### BUGGY CODE ###

Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]
ok = []
for i in range(2, 50001):
    for j in range(2, int((i**0.5)+1)):
        if i%j == 0:
            break
    else:
        ok.append(i)

for l, r in lr:
    cnt = 0
    for i in range(l, r+1, 2):
        if (i in ok) and ((i+1)/2 in ok):
            cnt += 1

    print(cnt)


### FIXED CODE ###

# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(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())
LR = [list(map(int, input().split())) for i in range(Q)]

primes = eratosthenes(10 ** 5+1)
primes[0] = False
primes[1] = False

ruiseki = [0] * (10**5 + 1)
for i in range(3, 10**5 + 1, 2):
    if (primes[i]) and (primes[int((i+1)/2)]):
        ruiseki[i] = ruiseki[i-2] + 1
    else:
        ruiseki[i] = ruiseki[i-2]

for l, r in LR:
    print(ruiseki[r] - ruiseki[l-2])