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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

n = int(input())
a = list(map(int, input().split()))
a.sort()
mod = 10 ** 9 + 7
ans = 0
b = [0] * n
for i in range(n - 1):
    g = gcd(a[i], a[i + 1])
    if i == 0:
        b[i] = a[i + 1] // g
        b[i + 1] = a[i] // g
        ans += b[i] + b[i + 1]
    else:
        c = a[i + 1] // g
        l = lcm(b[i], c)
        if not l == b[i]:
            ans *= l // b[i]
            ans %= mod
        c = l // c
        b[i + 1] = c * a[i] // g
        ans += b[i + 1]
    ans %= mod
print(ans if n >= 2 else 1)

### FIXED CODE ###

def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        c = 0
        while True:
            if not n % i == 0:
                ans.append([i, c])
                break
            n //= i
            c += 1
        if n == 1:
            break
    if n != 1:
        ans.append([int(n), 1])
    return ans

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
s = [0] * (5 * (10 ** 5))
for i in a:
    p = prime_factorize(i)
    for q in p:
        r = (q[0] - 1) // 2
        s[r] = max(s[r], q[1])
l = 1
for i in range(len(s)):
    l *= pow(max(2 * i + 1, 2), s[i], mod)
    l %= mod
ans = 0
for i in a:
    ans += pow(i, mod - 2, mod) * l % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

n = input()
a = list(map(int,input().split()))
max_a = max(a)
for i in range(max_a,0,-1):
    diff = [-1 if a[k]%i > 0 else 0 for k in range(len(a))]
    if sum(diff) == -1 or sum(diff) ==0:
        print(i)
        break

### FIXED CODE ###

import fractions
n = int(input())
a = [0] + list(map(int,input().split())) + [0]


#はじめと最初の値を代入
L = [0] * (n+2)
R = [0] * (n+2)

for i in range(n):
    L[i+1] = fractions.gcd(L[i], a[i+1])

for j in range(n,0,-1):
    R[j] = fractions.gcd(R[j+1],a[j])

#print(a)
#print(L)
#print(R)

print(max(fractions.gcd(L[k-1],R[k+1]) for k in range(1,len(L)-1)))
### BUGGY CODE ###

import math
from functools import reduce
def gcd_list(numbers):
  return reduce(math.gcd,numbers)
count=0
n=int(input())+1
for i in range(1,n):
  for j in range(1,n):
    for k in range(1,n):
      val=gcd_list([i,j,k])
      count+=val
print(count)

### FIXED CODE ###

import math
 
n=int(input())+1
ans=0
for i in range(1,n):
  for j in range(i,n):
    for k in range(j,n):
      if i==j and i==k:
        buff=1
      elif i==j:
        buff=3
      elif j==k:
        buff=3
      else:
        buff=6
      g1=math.gcd(i,j)
      g=math.gcd(k,g1)
      ans+=g*buff
print(ans)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
left = deque([])
right = deque([])
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')


### FIXED CODE ###

N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
left = set(left)
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
*A, = map(int, input().split())
*B, = map(int, input().split())
*C, = map(int, input().split())
AB = [a+b for a in A for b in B]
AB.sort(reverse=True)
AB = AB[:K]
ABC = [ab+c for ab in AB for c in C]
ABC.sort(reverse=True)
ABC = ABC[:K]
for abc in ABC:
    print(abc)


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
*A, = sorted(map(int, input().split()), reverse=True)
*B, = sorted(map(int, input().split()), reverse=True)
*C, = sorted(map(int, input().split()), reverse=True)
AB = [A[x] + B[y] for y in range(Y) for x in range(X)]
AB.sort(reverse=True)
AB = AB[:K]
ABC = [AB[x] + C[z] for z in range(Z) for x in range(len(AB))]
ABC.sort(reverse=True)
for k in range(K):
    print(ABC[k])
### BUGGY CODE ###

#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc123_d
import itertools

# input
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
# getans
arr = itertools.product(A, B, C)
arr = map(sum, arr)
arr = sorted(arr, reverse=True)
# output
for a in arr[:K]:
    print(a)


### FIXED CODE ###

#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc123_d
import itertools
import math

# input
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
# A = range(1000)
# B = range(1000)
# C = range(1000)
# getans
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
arr = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            arr.append(A[i]+B[j]+C[k])
#print(len(arr))
arr.sort(reverse=True)
# output
ans = '\n'.join(map(str, arr[:K]))
print(ans)
### BUGGY CODE ###

from bisect import*
N,*L=map(int,open(0).read().split());L.sort()
a=0
for i in range(N):
    for j in range(i+1,N):
      	a+=bisect_left(L[j+1:],L[i]+L[j])-bisect(L[j+1:],abs(L[i]-L[j]))
print(a)

### FIXED CODE ###

from bisect import*
N,*L=map(int,open(0).read().split());L.sort()
a=0
l=[]
r=[]
for i in range(1001):
    l.append(bisect_left(L,i))
    r.append(bisect(L,i))
for p in L:
    for q in L:
        x=p+q
        y=abs(p-q)
        a+=(l[x]if x<1001else N)-(r[y]if 0<y<1001else(y>1000)*N)
for p in L:
    x=2*p
    a-=3*(l[x]if x<1001else N)
print((a+2*N)//6)
### BUGGY CODE ###

def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(min(dp[N][H:H+MAX]))

### FIXED CODE ###

def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[inf for i in range(W+1)] for j in range(N+1)]
  dp[0][0]= 0
  #DP
  for i in range(N):
    for w in range(W+1):
      if 0 <= w-weight[i]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
H,N = map(int,input().split())
 
weight=[]
value=[]
for i in range(N):
    n,a=input().split()
    weight.append(int(n))
    value.append(int(a))
MAX = max(weight)
dp = knapsack(N,H+MAX,weight,value)
 
print(min(dp[N][H:H+MAX]))
### BUGGY CODE ###

N,K = map(int,input().split())
while N>0:
  N -= K
print(min(abs(N),N+K))
  

### FIXED CODE ###

N,K = map(int,input().split())
a = N//K
print(min(N-a*K,abs(N-(a+1)*K)))
### BUGGY CODE ###

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

sm = 0
for i in range(0, n):
    sm = sm + a[i]

min_dif = sm

p = 0
for i in range(n-3):
    p = p + a[i]
    if 4*p < sm:
        next
    q = 0
    for j in range(i+1, n-2):
        q = q + a[j]
        if 3*q < sm - p:
            next
        r = 0
        for k in range(j+1, n-1):
            r = r + a[k]
            if 2*r < sm - p - q:
                next
            s = 0
            for l in range(k+1, n):
                s = s + a[l]
            d = max([p, q, r, s])-min([p, q, r, s])
            min_dif = min([d, min_dif])

p = 0
for i in range(n-3):
    p = p + a[i]
    if 4*p <= sm - 3*min_dif or 4*p >= sm + 3*min_dif:
        next
    q = 0
    for j in range(i+1, n-2):
        q = q + a[j]
        if abs(p-q) >= min_dif or 4*q <= sm - 3*min_dif or 4*q >= sm + 3*min_dif:
            next
        r = 0
        for k in range(j+1, n-1):
            r = r + a[k]
            if abs(p-r) >= min_dif or abs(q-r) >= min_dif or 4*r <= sm - 3*min_dif or 4*r >= sm + 3*min_dif:
                next
            s = 0
            for l in range(k+1, n):
                s = s + a[l]
            d = max([p, q, r, s])-min([p, q, r, s])
            min_dif = min([d, min_dif])

print(min_dif)


### FIXED CODE ###

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

t = list(0 for i in range(n+1))
for i in range(1, n+1):
    t[i] = t[i-1] + a[i-1]

def sum_a(i, j):
    return t[j]-t[i]

min_dif = sum_a(0, n)

i = 0
k = 2
for j in range(2, n-1):
    u = sum_a(0, j) // 2
    while sum_a(0, i) < u:
        i = i + 1
    if abs(sum_a(0, i-1)-sum_a(i-1, j)) < abs(sum_a(0, i) - sum_a(i, j)): 
        i = i - 1
    p = sum_a(0, i)
    q = sum_a(i, j)

    u = sum_a(j, n) // 2
    while sum_a(j, k) < u:
        k = k + 1
    if abs(sum_a(j, k-1)-sum_a(k-1, n)) < abs(sum_a(j, k) - sum_a(k, n)): 
        k = k - 1
    r = sum_a(j, k)
    s = sum_a(k, n)

    min_dif = min(min_dif, max(p, q, r, s)-min(p, q, r, s))

print(min_dif)
### BUGGY CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
for i in range(2**n):
    x=0
    y=0
    for j in range(n):
        if (i>>j)&1:
            x+=v[j]
            y+=c[j]
    ans.append(x-y)
print(max(ans))


### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
for i in range(2**n):
    x=0
    y=0
    for j in range(n):
        if (i>>j)&1:
            x+=v[j]
            y+=c[j]
    ans.append(x-y)
print(max(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n, k = map(int, input().split())
p = list(map(int, input().split()))
np_p = np.array(p)

keep_val = 0
check = 0
for i in range(n-k+1):
    ss = np_p[i:i+k].sum()
    if keep_val < ss:
        check = i
        keep_val = ss
print(((np_p[check:check+k]+1)/2).sum())

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n, k = map(int, input().split())
p = list(map(int, input().split()))

summation = 0
exp_val = []
for i in range(n):
    summation += (p[i]+1)/2
    exp_val.append(summation)
exp_val.insert(0, 0)
#print(exp_val)

ans = 0
for i in range(n-k+1):
    m = exp_val[k+i] - exp_val[i]
    ans = max(ans, m)

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

num = input().split()
 
n = int(num[0])
y = int(num[1])

m = 0
g = 0
s = 0

flag = False


for i in range(n+1):
    if flag:
        break
    m = i
    
    for e in range(n+1):
        if flag:
            break
        g = e
        
        me = m * 10000
        ge = g * 5000
        
        tmpS =  y - (me+ge)
        
        if (tmpS / 1000) + (m+g) == n and me+ge+tmpS == y and (tmpS / 1000) >= 0:
            flag = True
            ma = m
            ga = g
            if tmpS / 1000 > 0:
                sa = tmpS / 1000
                sa = int(sa)
            else: 
                sa = 0
if flag:
    print(ma,ga,sa)
else:
    print(-1,-1,-1)



### FIXED CODE ###

num = input().split()
 
n = int(num[0])
y = int(num[1])

m = 0
g = 0
s = 0

flag = False


for i in range(n+1):
    if flag:
        break
    m = i
    
    me = m * 10000
    
    if (y - me) / 5000 <= n: 
    
        for e in range(n+1):
            if flag:
                break
            g = e
            
            ge = g * 5000
            
            tmpS =  y - (me+ge)
            
            if (tmpS / 1000) + (m+g) == n and me+ge+tmpS == y and (tmpS / 1000) >= 0:
                flag = True
                ma = m
                ga = g
                if tmpS / 1000 > 0:
                    sa = tmpS / 1000
                    sa = int(sa)
                else: 
                    sa = 0
if flag:
    print(ma,ga,sa)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

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

B = []
for j in range(n):
    B.append(j - A[j])

count = 0

for i in range(n):
    b = i + A[i]
    count += B[(i+1):].count(b)

print(count)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))

B = []
for j in range(n):
    B.append(j - A[j])

C = []
for i in range(n):
    C.append(i + A[i])

d = defaultdict(int)

for j in C:
    d[j] += 1

count = 0
for k in B:
    count += d[k]

print(count)

# 時間超過
# count = 0
# for i in range(n):
#     b = i + A[i]
#     count += B[(i+1):].count(b)
# print(count)
### BUGGY CODE ###

n, k = map(int, input().split())
p = map(int, input().split())
p_e = list(map(lambda x: (x + 1)* 0.5, p))

max_e = -1
for i in range(n - k + 1):
    v = sum(p_e[i:i+k])
    if max_e < v:
        max_e = v
print(max_e)

### FIXED CODE ###

n, k = map(int, input().split())
p = map(int, input().split())

p_e = [0] + [ (x + 1) * 0.5 for x in p]
p_p = [0]

for i in range(1, n+1):
    p_p.append(p_p[i-1] + p_e[i])

e_sum = [p_p[i] - p_p[i - k] for i in range(k, n+1)]
print(max(e_sum))
### BUGGY CODE ###

N, P = map(int, input().split())
if N == 1:
    print(P)
    exit()

p = int(P**(1/N)) + 1
n = 0
for i in range(1,p+1):
    if P % (i**N) == 0:
        n = i
print(n)

### FIXED CODE ###

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()

lim = int(p) + 1

dic = {}

def my(N,newP):
    for i in range(2,lim+1):
        while newP % i == 0:
            dic[i] = dic.get(i,0) + 1
            newP = newP // i
        if newP < i or i == lim:
            res = 1
            for j,k in dic.items():
                res *= j**(k//N)
            print(res)
            exit()
my(N,P)
### BUGGY CODE ###

# 移動Aで探索する方向
d_a = [(-1,0),(0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = list()
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i,j) not in (d_a+[(0,0)]):
            d_b += [(i,j)]

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+4, w+4), INF)
dist = [[INF for j in range(w+4)] for i in range(h+4)]

# マップ境界と壁を距離0にして探索させない
for i in range(len(dist)):
    dist[i][0] = 0
    dist[i][1] = 0
    dist[i][-1] = 0
    dist[i][-2] = 0
for j in range(len(dist[0])):
    dist[0][j] = 0
    dist[1][j] = 0
    dist[-1][j] = 0
    dist[-2][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+2][j+2] = 0

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置、終了位置を調整
si, sj = si+1, sj+1
ti, tj = ti+1, tj+1
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for di, dj in d_a:
        di, dj = di+i, dj+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for di, dj in d_b:
        di, dj = di+i, dj+j
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()

# 移動Aで探索する方向
d_a = [(-1,0), (0,-1),(1,0),(0,1)]
# 移動Bで探索する方向
d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]

# 距離情報を一番遠い値で初期化
#import numpy as np
INF = int(1e9)
#dist = np.full((h+2, w+2), INF)
dist = [[INF for j in range(w+2)] for i in range(h+2)]

# マップ境界と壁を距離0にして探索させない
for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='#': dist[i+1][j+1] = 0
#dist = [[INF for j in range(w)] for i in range(h)]

# 01-BFS探索用キュー
from collections import deque
q = deque()

# 開始位置
dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    # 移動Aによるコスト
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d
        q.appendleft((di, dj))
    # 移動Bによるコスト
    for v in range(len(d_b)):
        # マップ境界で2以上移動したときに、反対の境界に向かうように剰余を取る
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue # 探索済みコスト以上
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = str(input())
ls = [list(map(int,input().split())) for _ in range(q)]
c = 0
a = []
for i in range(n-1):
    if s[i] == "A":
        if s[i+1] == "C":
            a.append(i)
for j in range(q):
    (u,t) = (ls[j][0],ls[j][1])
    for k in a:
        if k in range(u-1,t-1):
            c += 1
    print(c)
    c = 0

### FIXED CODE ###

n,q = map(int,input().split())
s = str(input())
a = [0]
for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        a.append(a[-1]+1)
    else:
        a.append(a[-1])
for j in range(q):
    u,t = map(int,input().split())
    print(a[t-1]-a[u-1])
### BUGGY CODE ###

import sys
from bisect import bisect_left

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

ans = 0
for i in range(len(C)):
    c = C[i]
    b_idx = bisect_left(B, c)
    for j in range(b_idx):
        b = B[j]
        a_idx = bisect_left(A, b)
        ans += a_idx
print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.buffer.readline
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

cumsum = [0]
for i in range(len(B)):
    b = B[i]
    a_idx = bisect_left(A, b)
    cumsum.append(cumsum[i] + a_idx)
# print('cumsum', cumsum)

ans = 0
for i in range(len(C)):
    c = C[i]
    b_idx = bisect_left(B, c)
    ans += cumsum[b_idx]
print(ans)
### BUGGY CODE ###

import fractions
A, B = map(int, input().split())
GCD = fractions.gcd(A, B)
k = 1
cnt = 1
while GCD > 1:
  k += 1
  if GCD % k:
    continue
  cnt += 1
  while GCD % k == 0:
    GCD //= k
print(cnt)

### FIXED CODE ###

import fractions
A, B = map(int, input().split())
GCD = fractions.gcd(A, B)
k = 1
cnt = 1
while GCD > 1:
  k += 1
  if k ** 2 > GCD:
    cnt += 1
    break
  if GCD % k:
    continue
  cnt += 1
  while GCD % k == 0:
    GCD //= k
print(cnt)
### BUGGY CODE ###

N=int(input())
for h in range(1,3501):
  for n in range(1,3501):
    if 4*h*n-N*n-N*h!=0 and (N*h*n)%(4*h*n-N*n-N*h)==0 and (N*h*n)//(4*h*n-N*n-N*h)>0:
      print(h,n,(N*h*n)//(4*h*n-N*n-N*h))
      exit()

### FIXED CODE ###

N=int(input())
for h in range(1,3501):
  for n in range(1,3501):
    if 4*h*n-N*n-N*h>0:
      if (N*h*n)%(4*h*n-N*n-N*h)==0:
        print(h,n,(N*h*n)//(4*h*n-N*n-N*h))
        exit()
### BUGGY CODE ###

n=int(input())
l=list(map(int, input().split()))
s=set(l)
d=dict()

for x in s:
    d[x] = l.count(x)


for x in l:
    sum = 0
    for key in d.keys():
        a = d[key]
        if key == x:
            a -= 1

        sum += (a*(a - 1)) // 2

    print(sum)

### FIXED CODE ###

n=int(input())
l=list(map(int, input().split()))
s=set(l)
d=dict()

for x in l:
    d[x]=0
for x in l:
    d[x]+=1


sum = 0
for key in d.keys():
    a = d[key]
    sum += (a*(a - 1)) // 2


for x in l:
    print(sum - d[x] +1)
### BUGGY CODE ###

numq = int(input())
lis = [1]*100001
lis[0] = 0
lis[1] = 0
i = 2
while(i < 318):
  if lis[i] == 1:
    k = 2
    while(i*k < 100001):
      lis[i*k] = 0
      k += 1
  i += 1
for _ in range(numq):
  count = 0
  a,b = map(int,input().split())
  for i in range(a,b+1):
    if i % 2 == 1 and lis[i] == lis[(i+1)//2] == 1:
      count += 1
  print(count)


### FIXED CODE ###

numq = int(input())
lis = [1]*100001
lis[0] = 0
lis[1] = 0
i = 2
while(i < 318):
  if lis[i] == 1:
    k = 2
    while(i*k < 100001):
      lis[i*k] = 0
      k += 1
  i += 1
lis2 = [0]*100001

for i in range(1,100001):
  if i % 2 == 1 and lis[i] == lis[(i+1)//2] == 1:
    lis2[i] = lis2[i-1] + 1
  else:
    lis2[i] = lis2[i-1]

for _ in range(numq):
  a,b = map(int,input().split())
  print(lis2[b] - lis2[a-1])
### BUGGY CODE ###

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

ans, sumA2 = abs(sum(A) - 0), 0
for i in range(N):
    sumA2 += A[i]
    ans = min(ans, abs(sum(A) - sumA2 * 2))

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L, R, sumL_R = 0, N - 1, A[0] - A[N - 1]

while R - L > 1:
    if sumL_R < 0:
        L += 1
        sumL_R += A[L]
    else:
        R -= 1
        sumL_R -= A[R]
print(abs(sumL_R))
### BUGGY CODE ###

n = int(input())
ms = list(map(int, input().split()))
for i in range(0, 1000000001, 2):
  a = i
  for m in ms:
    a = 2 * m - a
  if i == a:
    result = i
    break

vv = ['%d' % a]
for m in ms[:-1]:
  a = 2 * m - a
  vv.append('%d' % a)
print(' '.join(vv))


### FIXED CODE ###

n = int(input())
ms = list(map(int, input().split()))

a = sum(ms) - 2 * sum(ms[1::2])
vv = ['%d' % a]
for m in ms[:-1]:
  a = 2 * m - a
  vv.append('%d' % a)
print(' '.join(vv))
### BUGGY CODE ###

N=int(input())
S=list(map(int, input().split()))
SS=[]
ans=0
n=0
for i in S:
  SS.append(i)
  if min(SS)>=S[n]:
    ans+=1
  n+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=list(map(int, input().split()))
Min=2*(10**5)
ans=0
for i in S:
  if Min>=i:
    Min=i
    ans+=1
    
print(ans)