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

n = int(input())
a = list(map(int, input().split()))
answer = sorted(a)[1]
for b in reversed(range(answer)):
    cnt = 2
    flag = True
    for i in range(n):
        if a[i] % answer != 0:
            cnt -= 1
        if cnt == 0:
            flag = False
    if flag:
        break
    answer -= 1
print(answer)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
answer = sorted(a)[1]
if n == 2:
    pass
else:
    for b in reversed(range(answer)):
        cnt = 2
        flag = True
        for i in range(n):
            if a[i] % answer != 0:
                cnt -= 1
            if cnt == 0:
                flag = False
                break
        if flag:
            break
        answer -= 1
print(answer)
### BUGGY CODE ###

def gen_prime():
	yield 2
	yield 3
	n=0
	while 1:
		yield n+5
		yield n+7
		n+=6


def resolve():
	l=list(range(55556))
	l[1]=0
	p=gen_prime()
	for i in p:
		if i in l:
			t=i+i
			while t<55556:
				l[t]=0
				t+=i
	prime=[i for i in l if i%5==1]
	n=int(input())
	ans=l[:n]
	x=''
	for i in ans:
		x+=i+' '
	print(x[:-1])
resolve()

### FIXED CODE ###

def gen_prime():
	yield 2
	yield 3
	n=0
	while 1:
		yield n+5
		yield n+7
		n+=6


def resolve():
	l=list(range(55556))
	l[1]=0
	p=gen_prime()
	for i in p:
		if i**2>55556:
			break
		if i in l:
			t=i+i
			while t<55556:
				l[t]=0
				t+=i
	prime=[i for i in l if i%5==1]
	n=int(input())
	ans=prime[:n]
	x=''
	for i in ans:
		x+=str(i)+' '
	print(x[:-1])

resolve()
### BUGGY CODE ###

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

for i in a:
    b=b*i

if b>10**18:
    print(-1)
else:
    print(b)


### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
b=1
a.sort()
for i in a:
    b=b*i
    
    if b>10**18:
        b=-1
        break
    
print(b)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
st=sx+sy*(W+2)
gl=gx+gy*(W+2)
c=['@']*(W+2)
for i in range(H):
    c.extend(['@']+list(input())+['@'])
c.extend(['@']*(W+2))
que=deque()
d=[INF]*(W+2)*(H+2)
direction=[[0]*4 for _ in range((H+2)*(W+2))]
que.append(st)
d[st]=0
di=(-1,1,W+2,-(W+2))
while que:
    v=que.popleft()
    for k in range(4):
        nv=v+di[k]
        if c[nv]=='.':
            if direction[v][k]>0:
                if d[nv]>d[v]:
                    direction[nv]=[0]*4
                    direction[nv][k]=direction[v][k]-1
                    d[nv]=d[v]
                    que.append(nv)
                elif d[nv]==d[v]:
                    direction[nv][k]=direction[v][k]-1
            else:
                if d[nv]>d[v]+1:
                    direction[nv]=[0]*4
                    direction[nv][k]=K-1
                    d[nv]=d[v]+1
                    que.append(nv)
                elif d[nv]==d[v]+1:
                    direction[nv][k]=K-1
print(d[gl] if d[gl]!=INF else -1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
st=sx+sy*(W+2)
gl=gx+gy*(W+2)
c=['@']*(W+2)
for i in range(H):
    c.extend(['@']+list(input())+['@'])
c.extend(['@']*(W+2))
que=deque()
dist=[INF]*(W+2)*(H+2)
que.append(st)
dist[st]=0
d=(-1,1,W+2,-(W+2))
while que:
    v=que.popleft()
    for k in range(4):
        nv=v
        for _ in range(K):
            nv+=+d[k]
            if c[nv]=='.' and dist[nv]>dist[v]:
                if dist[nv]==INF:
                    dist[nv]=dist[v]+1
                    que.append(nv)
            else:
                break
print(dist[gl] if dist[gl]!=INF else -1)
### BUGGY CODE ###

N = int(input())
str = "Christmas"
 
if N != 25:
	while N >= 22:
		str += " Eve"
		N += 1
        
print(str)

### FIXED CODE ###

N = int(input())
str = "Christmas"
 
if N != 25:
	while N < 25:
		str += " Eve"
		N += 1
        
print(str)
### BUGGY CODE ###

import sys 
input = sys.stdin.readline

n, m = map(int,input().split())
L, R = map(int,input().split())

ok = [i for i in range(n+1) if L<=i and i<=R]
ok2 = []

for i in range(m-1):
  l, r = map(int,input().split())
  for j in ok:
    if not(j < l or r < j):
      ok2.append(j)
  ok = ok2
  ok2 = []
      
print(len(ok))

### FIXED CODE ###

import sys 
input = sys.stdin.readline

n, m = map(int,input().split())
L = []
R = []

for i in range(m):
  l, r = map(int,input().split())
  L.append(l)
  R.append(r)
  
if min(R)-max(L) >= 0:
  print(min(R)-max(L)+1)
else:
  print(0)
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

N, M, S = map(int, input().split())
MAX = 10000
AB = [[None] * N for _ in range(N)]
for _ in range(M):
    U, V, A, B = map(int, input().split())
    U -= 1
    V -= 1
    AB[U][V] = AB[V][U] = (A, B)
CD = [tuple(map(int, input().split())) for _ in range(N)]
edges = [[] for _ in range(N*(MAX+1))]
for v in range(N):
    C, D = CD[v]
    for i in range(MAX):
        edges[v*(MAX+1)+i].append((min(v*(MAX+1)+i+C, (v+1)*(MAX+1)-1), D))
for u in range(N-1):
    for v in range(u+1, N):
        if not AB[u][v]:
            continue
        A, B = AB[u][v]
        for i in range(A, MAX+1):
            edges[u*(MAX+1)+i].append((v*(MAX+1)+i-A, B))
            edges[v*(MAX+1)+i].append((u*(MAX+1)+i-A, B))
dist = dijkstra(edges, N*(MAX+1), min(S, MAX))
for v in range(1, N):
    print(min(dist[v*(MAX+1):(v+1)*(MAX+1)]))

### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance

def main():
    N, M, S = map(int, input().split())
    AB = [[None] * N for _ in range(N)]
    s = 0
    for _ in range(M):
        U, V, A, B = map(int, input().split())
        U -= 1
        V -= 1
        AB[U][V] = AB[V][U] = (A, B)
        s += A
    MAX = s + 1
    CD = [tuple(map(int, input().split())) for _ in range(N)]
    edges = [[] for _ in range(N*MAX)]
    for v in range(N):
        C, D = CD[v]
        for i in range(MAX-1):
            edges[v*MAX+i].append((min(v*MAX+i+C, (v+1)*MAX-1), D))
    for u in range(N-1):
        for v in range(u+1, N):
            if not AB[u][v]:
                continue
            A, B = AB[u][v]
            for i in range(A, MAX):
                edges[u*MAX+i].append((v*MAX+i-A, B))
                edges[v*MAX+i].append((u*MAX+i-A, B))
    dist = dijkstra(edges, N*MAX, min(S, MAX-1))
    for v in range(1, N):
        print(min(dist[v*MAX:(v+1)*MAX]))
main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
def sumA(A):
  ans = 0
  for x in A.keys():
    ans += x * A[x]
  return ans

A = {}
for i in range(n):
  if a[i] in A.keys():
    A[a[i]] += 1
  else:
    A[a[i]] = 1

q = int(input())
for i in range(q):
  b,c = list(map(int, input().split()))
  if b in A.keys():
    if c in A.keys():
      A[c] += A[b]
      A[b] = 0
    else:
      A[c] = A[b]
      A[b] = 0
  print(sumA(A))



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())

A = [0] * 100001
for i in a:
  A[i] += 1

ans  = 0
for i in range(len(A)):
  ans += i * A[i]  

for n in range(q):
  b,c = list(map(int, input().split()))
  ans += (c * A[b]) - (b * A[b])
  A[c] += A[b]
  A[b] = 0
  print(ans)
### BUGGY CODE ###

s = input()
n = int(input())
for i in range(n):
    a = input().split()
    if len(a) == 1:
        s = s[::-1]
    else:
        t, c = int(a[1]),a[2]
        if t == 1:
            s = c+s
        else:
            s = s + c
print(s)

### FIXED CODE ###

s = input()
q = int(input())
qs = [input().split() for i in range(q)]
n = False
left= right = ""
for operation in qs:
    if operation[0] == '1':
        n = not n
    if operation[0] == '2':
        t , f, c = operation
        f = int(f)
        if n:
            f = 1 if f != 1 else 2
        if f == 1:
            left=c+left
        elif f == 2:
            right+=c
s = left+s+right
print(s[::-1] if n else s)
### BUGGY CODE ###

S = input()
count = 0
for i, s in enumerate(S):
    if s == 'B':
        count += S[i + 1:].count('W')
print(count)

### FIXED CODE ###

S = input()
count = 0
foundB = 0
for s in S:
    if s == 'W':
        count += foundB
    elif s == 'B':
        foundB += 1
print(count)
### BUGGY CODE ###

n,m = list(map(int,input().split()))
counter = 0
data = []
#入力処理
for i in range(m):
  data.append(input().split())
checkd = []
tmp = {}
for i in range(1,n+1):
  tmp[i] = 0

wa = 0
for i in range(m):
  if data[i][1] == "WA":
    tmp[int(data[i][0])] += 1
  elif ((data[i][1]) == "AC") and (int(data[i][0]) not in checkd):
    counter += 1
    checkd.append(int(data[i][0]))
    wa += tmp[int(data[i][0])]
    
print(counter,wa)

  
  



### FIXED CODE ###

n,m = list(map(int,input().split()))
counter = 0
data = []
tmp = {}#問題番号をkeyとしてWAをカウント

wa = 0
#入力処理
for _ in range(m):
  a,b = input().split() #入力処理
  if b == "WA": #解答がWA→tmpに問題番号をkeyとしてカウント
    if int(a) not in tmp:
      tmp[int(a)] = 0
    if tmp[int(a)] != -1:
      tmp[int(a)] += 1
  if int(a) not in tmp: #WA無しのACの対応 
    tmp[int(a)] = 0
  if (( b == "AC") and (tmp[int(a)] != -1)):#解答がACでtmp[問題番号]が出力済みでない場合
    counter += 1
    #checkd.append(int(a))
    wa += tmp[int(a)] #問題番号aの値をWAの合計に加算
    tmp[int(a)] = -1 #問題番号aが加算済み


"""
for i in range(m):
  if data[i][1] == "WA":
    if int(data[i][0]) not in tmp:
      tmp[int(data[i][0])] = 0
    tmp[int(data[i][0])] += 1  
  elif ((data[i][1]) == "AC") and (int(data[i][0]) not in checkd):
    counter += 1
    checkd.append(int(data[i][0]))
    if int(data[i][0] ) not in tmp:
      tmp[int(data[i][0])] = 0  
    wa += tmp[int(data[i][0])]
"""    
print(counter,wa)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# a = cmb(n,r,mod)

a.sort()
ans=0
if n==1 or k==1:
    print(0)
    exit()
# c=cmb(n-1,k-1,mod)
tmp=max(a)-min(a)
suuji=[[0,0] for i in range(tmp+1)]
low=min(a)
# for i in range(n):
#     print(a[i]-low)
#     suuji[a[i]-low][0]+=i
#     suuji[a[i]-low][1]+=c-i
for i in range(len(a)):
    ans+=a[i]*cmb(i,k-1,mod)
    ans-=a[i]*cmb(n-i-1,k-1,mod)
    ans%=mod
# print(suuji)
print(ans)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)
 
    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod
 
    def make_factorial_list(self, n):
 
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv
 
    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

a.sort()
ans=0
if n==1 or k==1:
    print(0)
    exit()
# c=cmb(n-1,k-1,mod)
comb = Combination(10**5)
# for i in range(n):
#     print(a[i]-low)
#     suuji[a[i]-low][0]+=i
#     suuji[a[i]-low][1]+=c-i

for i in range(len(a)):
    if i>=k-1:
        ans+=a[i]*comb(i,k-1)
        ans%=mod
    if n-i-1>=k-1:
        ans-=a[i]*comb(n-i-1,k-1)
        ans%=mod
    ans%=mod
# print(suuji)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0

max_A = max(A)
set_A = set(A)

for num in set_A:
    count_num = A.count(num)

    #望ましい数より大きい場合
    if count_num >= num:
        ans += count_num - num
    #望ましい数より小さい場合は0まで削る。
    else:
        ans += count_num

print(ans)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
ans = 0
before_num = A[0]
num_count = 1
A.append(-1)#一番大きい数を計算するとき用

for num in A[1:]:
    if num == before_num:
        num_count += 1
    else:
        if num_count >= before_num:
            ans += num_count - before_num
        else:
            ans += num_count
        num_count = 1
        before_num = num

print(ans)
### BUGGY CODE ###

h,w,m=map(int,input().split())
h_=[0]*(h+1)
w_=[0]*(w+1)
plot=[[] for _ in range(h+1)]
for _ in range(m):
    x,y=map(int,input().split())
    h_[x]+=1
    w_[y]+=1
    plot[x].append(y)   
x=max(h_)
y=max(w_)
a=[i for i,v in enumerate(h_) if v==x]
b=[j for j,q in enumerate(w_) if q==y]
u=0
c=0
for i in a:
    for j in b:
        if len(plot[i])==0:
          u+=0
        else:
          if j in plot[i]:
            u+=1  
        c+=1
ans=x+y
if u==c:
    print(ans-1)
else:
    print(ans)                


### FIXED CODE ###

h,w,m=map(int,input().split())
h_=[0]*(h+1)
w_=[0]*(w+1)
plot=set()
for _ in range(m):
    x,y=map(int,input().split())
    h_[x]+=1
    w_[y]+=1
    plot.add((x,y))
x=max(h_)
y=max(w_)
a=[i for i,v in enumerate(h_) if v==x]
b=[j for j,q in enumerate(w_) if q==y]
ans=x+y-1
c=False
for i in a:
    for j in b:
        if (i,j) not in plot:
          c=True
          break
    if c:
      break
if c:
  print(ans+1)
else:
  print(ans)
### BUGGY CODE ###

A,B,K = map(int,input().split())

for i in range(K):
    if A > 0:
        A -= 1
    elif B > 0:
        B -= 1
print(str(A)+' '+str(B))

### FIXED CODE ###

A,B,K = map(int,input().split())

if K >= A+B:
    print(str(0)+' '+str(0))

elif K < A:
    print(str(A-K)+' '+str(B))

elif K >= A:
    print(str(0)+' '+str(B-(K-A)))
### BUGGY CODE ###

import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

BIG = 999999


# # # # main start

n,m = inm()
fff = 2**n - 1
dp = [BIG] * (2**n)
a = []
s = []
for i in range(m):
  aa,bb = inm()
  c = inl()
  ss = 0
  c = [x-1 for x in c]
  for cc in c:
    ss |= (1<<cc)
  a.append(aa)
  s.append(ss)

dp = [BIG] * (2**n)
dp[0] = 0

for i in range(m):
  aa = a[i]
  ss = s[i]
  for j in range(2**n):
    dp[j|ss] = min(dp[j|ss], dp[j]+aa)

v = dp[2**n-1]
print(-1 if v>=BIG else v)


### FIXED CODE ###

import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

BIG = 999999


# # # # main start

n,m = inm()
fff = 2**n - 1
dp = [BIG] * (2**n)
a = []
s = []
for i in range(m):
  aa,bb = inm()
  c = inl()
  ss = 0
  c = [x-1 for x in c]
  for cc in c:
    ss |= (1<<cc)
  a.append(aa)
  s.append(ss)

dp = [BIG] * (2**n)
dp[0] = 0

for i in range(m):
  aa = a[i]
  ss = s[i]
  for j in range(2**n):
    dp[j|ss] = min(dp[j|ss], dp[j]+aa)

v = dp[2**n-1]
print(-1 if v>=BIG else v)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split())) 
ans = 0
ru = []

for i in range(1,n):
    ru.append(a[0] + a[i])
#print(ru)

tmp =  [j for j in range(len(ru))  if j+1 == ru[j]]
ans = ans + len(tmp)

for i in range(1,n-1):
    ru.pop(0)
    ru = [x- a[i-1] +a[i] for x in ru]
    #print(ru)
    tmp =  [j for j in range(len(ru)) if j+1 == ru[j]]
    ans = ans + len(tmp)


print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int, input().split())) 
ans = 0
ru = []

for i in range(n):
    ru.append(int(i + 1 + a[i]))

c = collections.Counter(ru)
#print(c)

for i in range(n):
    tmp = i + 1 - a[i]
    ans += c[tmp]

print(ans)
### BUGGY CODE ###

from statistics import median


N = int(input())
X = list(map(int, input().split()))
for i in range(N):
    x = X[:]
    del x[i]
    print(median(x))

### FIXED CODE ###

from statistics import median


N = int(input())
X = list(map(int, input().split()))
medi_X = median(X)
sort_X = sorted(X)

for x in X:
    if x < medi_X:
        print(sort_X[int((N + 1) / 2)])
    else:
        print(sort_X[int(((N + 1) / 2) - 1)])
### BUGGY CODE ###

import functools
#import math
import fractions

N = int(input())
A = list(map(int,input().split()))

#gcd_all = functools.reduce(math.gcd, A)
gcd_all = functools.reduce(fractions.gcd, A)

for i in range(N):
    #gcd_1 = functools.reduce(math.gcd, list)
    gcd_1 = functools.reduce(fractions.gcd, (A[:i]+A[i+1:]))
    if gcd_1 >= gcd_all:
        gcd_all = gcd_1

print(gcd_all)


### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

L = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

max_m = 0
for i in range(N):
    m = gcd(L[i], R[i+1])
    if max_m < m:
        max_m = m
print(max_m)
### BUGGY CODE ###

N = int(input())
S = input()
cnt = 0
all_set = set()
for i in range(1,N-1):
    before_set = set(S[:i])
    after_set = set(S[i+1:])
    for j in before_set:
        for k in after_set:
            all_set.add(j+S[i]+k)
print(len(all_set))

### FIXED CODE ###

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

s = set()
L = [[set() for i in range(2)] for j in range(N+1)]

ans = set()

for i in range(N):
    L[i+1][0].add(S[i])
    for k in L[i][0]:
        L[i+1][0].add(k)
        L[i+1][1].add(k + S[i])
    for k in L[i][1]:
        L[i+1][1].add(k)
        ans.add(k + S[i])

print(len(ans))
### BUGGY CODE ###

n= int(input())
lst = [int(i) for i in input().split()]
lst = sorted(lst)
count = 0
d_lst = []
for i in range(len(lst)):
    for j in range(i+1,len(lst)):
    # print(i,j)
        a = lst[i] * lst[j]
        if lst[j] in d_lst:
            continue
        else:
            if lst[i] == lst[j]:
                d_lst.append(lst[j])
                count += a
            else:
                count += a
    
if count > ( 10**9 + 7 ):
    print(count % (10**9 + 7))
else:
    print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ruiseki = 0
count = 0
for i in range(n-1):
    ruiseki += a[i]
    count += ruiseki * a[i+1]
mod = 10**9 + 7
if count >= mod:
    print(count%mod)
else:
    print(count)
### BUGGY CODE ###

from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})
#print(weight,link)
for v in range(vertice):
    goal = v
    queue = []
    heapq.heappush(queue,[0,source])
    went = set()

    while queue != []:
        #print(queue)
        now_cost,here = heapq.heappop(queue)
        #print(now_cost,here,queue)
        if here == goal:
            print(now_cost)
            break

        can_go = link[here]
        not_went = set(can_go) - went
        #print(v,here,now_cost,not_went,queue)
        for nw in not_went:
            next_cost = now_cost + weight[here][nw]
            heapq.heappush(queue,(next_cost,nw))
        went = went | {here}
    else:
        print("INF")

### FIXED CODE ###

import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
from collections import defaultdict
vertices, edges, start = map(int, readline().split())
connect = defaultdict(list)
cost = defaultdict(dict)
answer = ["INF" for n in range(vertices)]
for _ in range(edges):
    s, t, w = map(int, readline().split())
    connect[s].append(t)
    cost[s].update({t:w})
 
 
now = start
weight = 0
p_queue = []
heappush(p_queue, (0, now))
visited = set()
while p_queue:
    weight, now = heappop(p_queue)
    if now in visited:
        continue
    visited |= {now}
    answer[now] = weight
    for c in connect[now]:
        if c not in visited:
            heappush(p_queue, (weight + cost[now][c], c))
for a in answer:
    print(a)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
s = 0

nL = sorted(L)

for i in range(0, N-2):
	for j in range(i+1, N-1):
		s += sum(x<nL[i]+nL[j] for x in nL[j+1:])
		
print(s)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
s = 0

L = sorted(L)

for c in reversed(range(2, N)):
	for b in reversed(range(1, c)):
		a = bisect.bisect_right(L, L[c]-L[b])
		if a<b:
			s += b-a
print(s)
### BUGGY CODE ###

import math
q = int(input())
list_range = [list(map(int, input().split())) for _ in range(q)]

max_range = math.sqrt(10**5)
list_search = [i for i in range(2, 10**5 + 1)]
list_prime = []
while list_search[0] <= max_range:
  list_prime.append(list_search[0])
  temp = list_search[0]
  list_search = [i for i in list_search if i % temp != 0]
list_prime.extend(list_search)

list_satisfy = []
for one_prime in list_prime:
  if one_prime * 2 > 10**5:
    break
  if one_prime * 2 - 1 in list_prime:
    list_satisfy.append(one_prime * 2 - 1)

result = [0 for _ in range(q)]
for one_num in list_satisfy:
  for i in range(q):
    if list_range[i][0] <= one_num <= list_range[i][1]:
      result[i] += 1
for one_result in result:
  print(one_result)

### FIXED CODE ###

q = int(input())
list_range = [list(map(int, input().split())) for _ in range(q)]

list_flag_prime = [1 for i in range(10**5+1)]
list_flag_prime[0:2] = [0, 0]
for i in range(2, 10**5+1):
  if list_flag_prime[i] == 1:
    for j in range(2*i, 10**5+1, i):
      list_flag_prime[j] = 0

list_subj = [0 for i in range(10**5+1)]
for i in range(3, 10**5+1, 2):
  if list_flag_prime[i] == 1 & list_flag_prime[int((i+1)/2)] == 1:
    list_subj[i] += 1

list_satisfy = [0 for i in range(10**5+1)]
for i in range(1, 10**5+1):
  list_satisfy[i] += list_satisfy[i-1] + list_subj[i]

for l, r in list_range:
  print(list_satisfy[r] - list_satisfy[l-1])