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

s = input()
t = input()
len_s = len(s)
len_t = len(t)

dp = {}
for i in range(-1, len_s):
    dp[(i, -1)] = 0
for j in range(-1, len_t):
    dp[(-1, j)] = 0

for i in range(len_s):
    for j in range(len_t):
        char = s[i]
        if char == t[j]:
            dp[(i, j)] = dp[(i-1, j-1)] + 1
        else:
            dp[(i, j)] = max(dp[(i-1, j)], dp[(i, j-1)])

answer = ''
i, j = len_s - 1, len_t - 1
now = dp[(i, j)]
while i > -1 and j > -1:
    if dp[(i-1, j)] == now:
        i -= 1
        continue
    if dp[(i, j-1)] == now:
        j -= 1
        continue
    answer += s[i]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])


### FIXED CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        char = s[i-1]
        if char == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

answer = ''
i, j = len(s), len(t)
now = dp[i][j]
while i > 0 and j > 0:
    if dp[i-1][j] == now:
        i -= 1
        continue
    if dp[i][j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])
### BUGGY CODE ###

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

result = []

for i in range(N):
    ind = A.index(min(A))
    result.append(str(ind+1))
    A[ind] = N + 1

print(" ".join(result))

### FIXED CODE ###

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

new_A = list(enumerate(A, 1))
sorted_A = sorted(new_A, key=lambda new_A:new_A[1])

for num in sorted_A:
    print(num[0], end=" ")
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=sorted([int(i) for i in input().split()],reverse=True)
b=sorted([int(i) for i in input().split()],reverse=True)
c=sorted([int(i) for i in input().split()],reverse=True)
ab=[]
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort(reverse=True)
ab=ab[:k]
l=len(ab)
abc=[]
for i in range(l):
    for j in range(z):
        abc.append(ab[i]+c[j])
abc.sort(reverse=True)
for i in range(k):
    print(abc[i])


### FIXED CODE ###

import heapq
x,y,z,k=map(int,input().split())
#heapqは小さい順にしか並べられないので、-をつければ大きい順になる
a=sorted([-int(i) for i in input().split()])
b=sorted([-int(i) for i in input().split()])
c=sorted([-int(i) for i in input().split()])
check=set()
ans=[]
heapq.heappush(ans,(a[0]+b[0]+c[0],0,0,0))
check.add((0,0,0))
for i in range(k):
    h=heapq.heappop(ans)
    print(-h[0])
    if h[1]+1<x:
        if (h[1]+1,h[2],h[3]) not in check:
            heapq.heappush(ans,(a[h[1]+1]+b[h[2]]+c[h[3]],h[1]+1,h[2],h[3]))
            check.add((h[1]+1,h[2],h[3]))
    if h[2]+1<y:
        if (h[1],h[2]+1,h[3]) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]+1]+c[h[3]],h[1],h[2]+1,h[3]))
            check.add((h[1],h[2]+1,h[3]))
    if h[3]+1<z:
        if (h[1],h[2],h[3]+1) not in check:
            heapq.heappush(ans,(a[h[1]]+b[h[2]]+c[h[3]+1],h[1],h[2],h[3]+1))
            check.add((h[1],h[2],h[3]+1))
'''
while len(ans)!=0:
    print(heapq.heappop(ans)[0])
'''
### BUGGY CODE ###

N, = map(int, input().split())
R = [0] * (N**2+1)
V = [0] * (N**2+1)
X = list(map(int, input().split()))
for ai in range(N**2):
    i, j = divmod(ai, N)
    R[ai+1] = min([i, N-i-1, j, N-j-1])

r = 0
for a in X:
    r += R[a]
    V[a] = 1
    stack=[a]
    while stack:
        v = stack.pop()
        i, j = divmod(v-1, N)
        ccs = []
        if v>N:
            ccs.append(v-N)
        if v<N**2+1-N:
            ccs.append(v+N)
        if v%N:
            ccs.append(v+1)
        if v%N!=1:
            ccs.append(v-1)
        for u in ccs:
            if R[v]>=R[u] or ((1-V[v]) and R[v]+1 >= R[u]):
                continue
            R[u] -= 1
            stack.append(u)
print(r)


### FIXED CODE ###

N, = map(int, input().split())
R = [0] * (N**2+1)
V = [0] * (N**2+1)
X = list(map(int, input().split()))
for ai in range(N**2):
    i, j = divmod(ai, N)
    R[ai+1] = min([i, N-i-1, j, N-j-1])

r = 0
for a in X:
    r += R[a]
    V[a] = 1
    stack=[a]
    while stack:
        v = stack.pop()
        ccs = []
        if v>N:
            ccs.append(v-N)
        if v<N**2+1-N:
            ccs.append(v+N)
        if v%N:
            ccs.append(v+1)
        if v%N!=1:
            ccs.append(v-1)
        for u in ccs:
            if R[v]>=R[u] or ((1-V[v]) and R[v]+1 >= R[u]):
                continue
            R[u] -= 1
            stack.append(u)
print(r)
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
 
 
def main():
    N = int(input().strip())
    divisors = set()
    ans = set()
    l = [int(i) for i in input().strip().split()]
    heapq.heapify(l)
 
    for _ in range(N):
        n = heapq.heappop(l)
 
        if n in divisors:
            if n in ans:
                ans.remove(n)
            continue
 
        divs = make_divisors(n)
 
        for d in divs:
            if d in divisors:
                divisors.add(n)
                break
        else:
            divisors.add(n)
            ans.add(n)
 
    return len(ans)
 

if __name__ == "__main__":
    print(main())

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    l = [int(i) for i in input().strip().split()]
    ans = 0
    m = max(l)
    dp = [0] * (m+1)

    for n in l:
        for j in range(n, m + 1, n):
            dp[j] += 1

    for n in l:
        if dp[n] == 1:
            ans += 1

    return ans


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

import sys
sys.setrecursionlimit(10000)
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]

memo = [[[0] * 4 for _ in range(W)] for _ in range(H)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y, i):
	nx = x + dx[i]
	ny = y + dy[i]
	if nx >= 0 and nx < H and ny >= 0 and ny < W and memo[nx][ny][i] > 0:
		memo[x][y][i] = memo[nx][ny][i] + 1
		return memo[x][y][i]
	elif nx >= 0 and nx < H and ny >= 0 and ny < W and S[nx][ny] == '.':
		memo[x][y][i] = dfs(nx, ny, i) + 1
		return memo[x][y][i]
	else:
		return 0
		
ans = 0

for sx in range(H):
	for sy in range(W):
		if S[sx][sy] == '.':
			tmp = 1
			for j in range(4):
				tmp += dfs(sx, sy, j)
				
			if tmp > ans:
				ans = tmp
				
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
H, W = map(int, input().split())
S = [input() for _ in range(H)]
R = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == '.':
			if j > 0:
				L[i][j] = L[i][j - 1] + 1
			elif j == 0:
				L[i][j] = 1
				
			if i > 0:
				U[i][j] = U[i - 1][j] + 1
			elif i == 0:
				U[i][j] = 1
		
		if S[i][W - j - 1] == '.':
			if j > 0:
				R[i][W - j - 1] = R[i][W - j] + 1
			elif j == 0:
				R[i][W - j - 1] = 1
		
		if S[H - i - 1][j] == '.':
			if i > 0:
				D[H - i - 1][j] = D[H - i][j] + 1
			elif i == 0:
				D[H - i - 1][j] = 1
			
ans = 0
for i in range(H):
	for j in range(W):
		tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
		if tmp > ans:
			ans = tmp
			
print(ans)
### BUGGY CODE ###

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
cnt = 0
        
while len(arr):
  i = arr[0]
  original = True
  for j in arr[1:]:
    if j % i == 0:
      arr.remove(j)
      if i == j:
        original = False
  if original:
    cnt += 1
  arr.remove(i)
    

print(cnt)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0]*(m+1)
cnt = 0
        
for i in arr:
  for j in range(i, m+1, i):
    li[j] += 1

for i in arr:
  if li[i] == 1:
    cnt += 1

print(cnt)
### BUGGY CODE ###

# D Knapsack 1


n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(dp, wv_list, i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(dp, wv_list, i-1, j)
    else:
        _ret = max(dp_solve(dp, wv_list, i-1, j), dp_solve(dp, wv_list, i-1, j-_w) + _v)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(dp, wv_list, n, w))

### FIXED CODE ###

# D Knapsack 1

from collections import deque

n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(w+1):
        if j-_w < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-_w]+_v)

print(dp[n][w])
### BUGGY CODE ###

N, M = map(int,input().split())
for i in range(M // N + 1)[::-1]:
    if M % i == 0:
        print(i)
        break

### FIXED CODE ###

N, M = map(int,input().split())
a, b = 1, M
divisor = []
while a <= b:
    if a * b == M:
        divisor.append(a)
        divisor.append(b)
    a = M // b + 1
    b = M // a
divisor.sort()
for i in divisor:
    if i >= N:
        print(M // i)
        break
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
s = sorted(set(A))
if len(A) == 1:
    print(1)
else:
    lst = []
    ans = 0
    for i in range(len(s)):
        m = s[i]/2
        flg = True
        for p in lst:
            if s[i]%p == 0:
                flg = False
                break
            elif m < p:
                break
        if flg:
            lst.append(s[i])
            if counter[s[i]] == 1:
                ans += 1
    print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
s = set(A)
counter = Counter(A)
A.sort()
ans = [1]*(10**6+1)
for i in range(1,10**6+1):
    if i in s and ans[i]:
        tmp = i
        cnt = 2
        while tmp*cnt <= 10**6:
            ans[tmp*cnt] = 0
            cnt += 1
    else:
        ans[i] = 0
    if counter[i] != 1:
        ans[i] = 0
print(sum(ans)-1)
### BUGGY CODE ###

N = input()
num = len(N)
ans = 0
for i in range(0,num-3):
  for j in range(i+3,num):
    if j == i + 3:
      s = int(N[i:j+1])
    else:
      s = t*10 + int(N[j])
    t = s% 2019
    if t == 0:
      ans += 1
print(ans)

### FIXED CODE ###

N = input()
num = len(N)
mod_sum = [0]*2019
mod_sum[0] = 1
ans = 0
a = 0
d = 1
for i in range(num):
  a = (a + int(N[-i-1])*d)%2019
  d = (d*10)%2019
  mod_sum[a] += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

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

x = 1000000000000000000
res = 1

for val in A:
    res = res * val

print(res if res <= x else '-1')


### FIXED CODE ###

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

x = 1000000000000000000
res = 1

A.sort(reverse=True)

if A.count(0) > 0:
    print('0')
    exit()

for val in A:
    res = res * val
    if res > x:
        print('-1')
        break
else:
    print(res)
### BUGGY CODE ###

import numpy as np
import copy

N, x = map(int,raw_input().split())
A = map(int,raw_input().split())

B = copy.deepcopy(A)
m = sum(B)
for idx in xrange(1,N):
  A = np.append(A, A[0])
  A = np.delete(A, 0)
  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)

### FIXED CODE ###

import time
import numpy as np
import copy

tflag = False
if tflag:
  N = 2000
  m = 1000000000
  x = np.random.randint(m)
  A = list(np.random.randint(m,size=(N)))
  st = time.time()
else:
  N, x = map(int,raw_input().split())
  A = map(int,raw_input().split())

#B = copy.deepcopy(A)
B = A
A = A + A
m = sum(B)
for idx in xrange(1,N):
  for jdx in xrange(N):
    if B[jdx] > A[jdx+N-idx]:
      B[jdx] = A[jdx+N-idx]
#  A = np.append(A, A[0])
#  A = np.delete(A, 0)
#  B = np.fmin(B,A)
  m = min(sum(B)+idx*x, m)

print int(m)
### BUGGY CODE ###

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

ans = 1
for i in range(1, N):
    tmp = min(P[:i])
    if tmp >= P[i]:
        ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
v = P[0]
for i in P:
    if i <= v:
        ans += 1
        v = i
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = []
h2 = []
ans = 10**10
for i in range(N):
  tmp = int(input())
  h.append(tmp)
h = sorted(h)
for i in range(N-K+1):
  h2 = h[i:i+K]
  ans = min(max(h2) - min(h2),ans)
print(str(ans))

### FIXED CODE ###

N,K = map(int,input().split())
h = []
ans = 10**10
for i in range(N):
  tmp = int(input())
  h.append(tmp)
h = sorted(h)
for i in range(N-K+1):
  h2 = h[i]
  h3 = h[i+K-1]
  ans = min(h3 - h2,ans)
print(str(ans))
### BUGGY CODE ###

R,C,K = map(int,input().split())
V = [[0 for c in range(C+1)] for r in range(R+1)]
r_list = [False for r in range(R+1)]
c_list = [False for c in range(C+1)]
for i in range(K):
	r,c,v = map(int,input().split())
	V[r][c] = v
	r_list[r] = True
	c_list[c] = True


r_map = {}
cnt = 0
for i in range(R+1):
	if r_list[i]:	
		cnt += 1
		r_map[i] = cnt
r_len = cnt

c_map = {}
cnt = 0
for i in range(C+1):
	if c_list[i]:
		cnt += 1
		c_map[i] = cnt
c_len = cnt

new_v = [[0 for i in range(c_len+1)] for j in range(r_len+1)]
for r in range(R+1):
	for c in range(C+1):
		if V[r][c] > 0:
			new_v[r_map[r]][c_map[c]] = V[r][c]

V = new_v
R = r_len
C = c_len

dp = [[[0 for i in range(4)] for j in range(C+1)] for k in range(R+1)]
for r in range(1, R+1):
	for c in range(1, C+1):
		v = V[r][c]
		under_val = max(dp[r-1][c])
		dp[r][c][0] = max(under_val, dp[r][c-1][0])
		if v > 0:
			dp[r][c][1] = max(under_val + v, dp[r][c-1][0] + v, dp[r][c-1][1])
			dp[r][c][2] = max(dp[r][c-1][1] + v, dp[r][c-1][2])
			dp[r][c][3] = max(dp[r][c-1][2] + v, dp[r][c-1][3])
		else:
			dp[r][c][1] = dp[r][c-1][1]
			dp[r][c][2] = dp[r][c-1][2]
			dp[r][c][3] = dp[r][c-1][3]
print(max(dp[-1][-1]))

### FIXED CODE ###

R,C,K = map(int,input().split())
V = [[0 for c in range(C+1)] for r in range(R+1)]
for i in range(K):
	r,c,v = map(int,input().split())
	V[r][c] = v

dp = [[0 for i in range(4)] for j in range(C+1)]
for r in range(1, R+1):
	for c in range(1, C+1):
		v = V[r][c]
		under_val = max(dp[c])
		dp[c][0] = max(under_val, dp[c-1][0])
		if v > 0:
			dp[c][1] = max(under_val + v, dp[c-1][0] + v, dp[c-1][1])
			dp[c][2] = max(dp[c-1][1] + v, dp[c-1][2])
			dp[c][3] = max(dp[c-1][2] + v, dp[c-1][3])
		else:
			dp[c][1] = dp[c-1][1]
			dp[c][2] = dp[c-1][2]
			dp[c][3] = dp[c-1][3]
print(max(dp[-1]))
### BUGGY CODE ###

s=input()
l=[0]*2019
t=0
ans=0
for i in range(len(s)):
    t=(t+(10**i)*int(s[-1-i]))%2019
    l[t]+=1
for i in l:
    ans+=(i*(i-1))//2
print(ans+l[0])

### FIXED CODE ###

s=list(input())
l=[0]*2019
t=0
ans=0
for i in range(len(s)):
    t=(t+pow(10,i,2019)*int(s[-1-i]))%2019
    l[t]+=1
for i in l:
    ans+=(i*(i-1))//2
print(ans+l[0])
### BUGGY CODE ###

from collections import defaultdict 

N,M=map(int,input().split())

if M == 0:
  print(-1)
  exit()

INF = 10**20
pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
G = defaultdict(dict)
lines = [set() for _ in range(N)]
for p,q,c in pqc:
  G[(p,c)][(q,c)] = G[(q,c)][(p,c)] = 0
  lines[p].add(c)
  lines[q].add(c)
  
for v in range(N):
  if len(lines[v])>1:
    tmp = list(lines[v])
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        G[(v,tmp[i])][(v,tmp[j])] = G[(v,tmp[j])][(v,tmp[i])] = 1
        
def dijkstra(start = 0):
    from heapq import heappop, heappush
    d = defaultdict(lambda:INF)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]: continue
        for u in G[v].keys():
            if d[u] > d[v] + G[v][u]:
                d[u] = d[v] + G[v][u]
                heappush(que, (d[u], u))
    return d

for c in lines[0]:
  G[(0,-1)][(0,c)] = 1
for c in lines[N-1]:
  G[(N-1,c)][(N-1,-1)] = 0
  
d = dijkstra((0,-1))
ans = d[(N-1,-1)]
print(ans if ans < INF else -1)

### FIXED CODE ###

def main():
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

from bisect import bisect_right, bisect_left

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

ans = 0
for i, a in enumerate(L):
    for j, b in enumerate(L[i + 1:], start=i + 1):
        left = bisect_right(L, abs(a - b))
        right = bisect_left(L, a + b)
        ans += right - left

        if left <= i < right:
            ans -= 1
        if left <= j < right:
            ans -= 1

print(ans // 3)


### FIXED CODE ###

from bisect import bisect_left

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

ans = 0
for i, A in enumerate(L):
    for j, B in enumerate(L[i + 1:], start=i + 1):
        right = bisect_left(L, A + B)
        ans += right - j - 1

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

N = int(input())
res = 0
p = list(map(int, input().split()))
for i in range(N):
    mini = min(p[:(i+1)])
    if mini >= p[i]:
        res += 1    
print(res)

### FIXED CODE ###

N = int(input())
res = 0
p = list(map(int, input().split()))
mini = p[0]
for i in range(N):
    mini = min(mini, p[i])
    if mini >= p[i]:
        res += 1    
print(res)
### BUGGY CODE ###

N = int(input())
S = input()
min = S[0:N].count('#')
for i in range(0, N):
    if min > S[0:i + 1].count('#') + S[i + 1:N].count('.'):
        min = S[0:i + 1].count('#') + S[i + 1:N].count('.')
if N == 1:
    min = 0
print("{}".format(min))


### FIXED CODE ###

N = int(input())
S = input()
count = S[0:N].count('.')
min = count
for i in range(0, N):
    if S[i:i + 1] == '#':
        count += 1
    else:
        count -= 1
    if count < min:
        min = count
if N == 1:
    min = 0
print("{}".format(min))
### BUGGY CODE ###

import numpy as np

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

count = 0
for i in range(n):
    ans = a[i] % np.array(a)
    if np.count_nonzero(ans == 0) == 1:
        count += 1

print(count)

### FIXED CODE ###

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

a_max = a[-1]
dp = [1]*a_max

for i in set(a):
    j = 2
    while i*j <= a_max:
        dp[i*j-1] = 0
        j += 1

a.append(0)
ans = 0
for i in range(n):
    if dp[a[i]-1] and a[i-1] != a[i] and a[i] != a[i+1]:
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque

N = int(input())
A = [deque(int(e)-1 for e in input().split()) for _ in range(N)]

#ad = [[0] * N for _ in range(N)]
game = 0

for d in range(1,N*(N-1)//2+1):
    #print("---------{}日目---------".format(d))
    matched = [0] * N
    for i in range(N):
        if matched[i]:
            continue
        if not A[i]:
            continue
        # 相手の候補
        j = A[i][0]
        if not A[j]:
            continue
        # お互いに最優先で今日中に試合をしていないなら試合をする
        if A[j][0] == i and not matched[j]:
            #print("{}と{}が試合".format(i+1,j+1))
            A[i].popleft()
            A[j].popleft()
            matched[i] = 1
            matched[j] = 1
            #ad[i][j] = 1
            #ad[j][i] = 1
            game += 1
    if game == N*(N-1)//2:
        print(d)
        exit()

print(-1)

### FIXED CODE ###

from collections import deque

N = int(input())
ad = [[] for _ in range(N*N)]
num = [0] * (N*N)

for i in range(N):
    a = [int(e)-1 for e in input().split()]
    for k in range(N-2):
        j = a[k]
        nj = a[k+1]
        v = N*max(i,j) + min(i,j)
        nv = N*max(i,nj) + min(i,nj)
        ad[v].append(nv)
        num[nv] += 1

S = deque()
L = []

for v in range(N*N):
    if num[v] == 0:
        S.append((v,1))

while S:
    v, d = S.popleft()
    L.append(d)
    for nv in ad[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append((nv, d+1))

if len(L) != N*N:
    print(-1)
    exit()

ans = max(L)
print(ans)
### BUGGY CODE ###

def solve():
    import sys
    n, *s = map(int, sys.stdin.read().split())
    for i in range(n):
        t = s[:i] + s[i + 1:]
        print(max(t))


solve()


### FIXED CODE ###

def solve():
    from bisect import bisect_left
    import sys
    n, *s = map(int, sys.stdin.read().split())
    t = sorted(s)
    for ss in s:
        x = bisect_left(t, ss)
        if x == n - 1:
            print(t[-2])
        else:
            print(t[-1])



solve()
### BUGGY CODE ###

def getinputdata():

    array_result = []    
    data = input()
    array_result.append(data.split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

x=arr_data[0][0]

cnt=10**10000
for i in range(cnt):
    
    if "ST" in x:
        
        x=x.replace("ST","")

    else:
        break

print(len(x))


### FIXED CODE ###

from collections import deque
def getinputdata():

    array_result = []    
    data = input()
    array_result.append(data.split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

x=arr_data[0][0]

b = deque([])

for v in x:
    
    if v=="S":
        
        b.appendleft(v)
        
    elif v=="T" and (len(b)==0 or b[0]=="T"):
        
        b.appendleft(v)
        
    else:
            
        b.popleft()
            
print(len(b))