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

def main():
    n = input()
    for i in xrange(n):
        X = raw_input()
        Y = raw_input()
        print lcs(X,Y)

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    c = [[0]*(n+1) for i in xrange(m+1)]

    for i in xrange(m):
        for j in xrange(n):
            if X[i] == Y[j]:
                c[i+1][j+1] = c[i][j] + 1
            else:
                if c[i][j+1] >= c[i+1][j]:
                    c[i+1][j+1] = c[i][j+1]
                else:
                    c[i+1][j+1] = c[i+1][j]
    return c[m][n]
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = input()
    for i in xrange(n):
        X = raw_input()
        Y = raw_input()
        print lcs(X,Y)

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    r1 = [0 for i in xrange(n+1)]
 
    for i in xrange(m):
        r0 = r1[:]
        for j in xrange(n):
            if X[i] == Y[j]:
                r1[j+1] = r0[j] + 1
            elif r0[j+1] < r1[j]:
                r1[j+1] = r1[j]
    return r1[-1]

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

a = input()
n = int(input())
for i in range(n):
    q = input()
    if q == "1":
        a = a[::-1]
    else:
        q,f,c = q.split()
        if f == "1":
            a = c+a
        else:
            a = a+c
print(a)

### FIXED CODE ###

a = input()
n = int(input())
rev = False
front = []
back = []
q = [input() for i in range(n)]
for i in q:
    if i == "1":
        rev = not rev
    else:
        i,f,c = i.split()
        if rev == False:
            if f == "1":
                front.append(c)
            else:
                back.append(c)
        else:
            if f == "1":
                back.append(c)
            else:
                front.append(c)
if rev == False:
    print("".join(list(reversed(front))+[a]+back))
else:
    print("".join(list(reversed(back))+[a[::-1]]+front))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
a = [0] * (N+1)
for i in range(N):
    a[i] = list(map(int, input().split()))
dp = np.zeros((N+1, 3), dtype=np.int64)

for n in range(N):
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            dp[n+1][i] = max(dp[n+1][i], dp[n][j] + a[n][i])
ans = max(dp[N])

print(ans)

### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

A, B, C = 0, 0, 0 #最後に各活動を行った幸福度の和
for _ in range(N):
    a, b, c = map(int, input().split())
    A, B, C = max(B, C) + a, max(C, A) + b, max(A, B) + c
ans = max(A, B, C)

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

N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A,reverse = True)
dp = []
for _ in range(M):
  A[0] //= 2
  A = sorted(A,reverse = True)
print(sum(A))

### FIXED CODE ###

from math import ceil
from heapq import heappop,heappush
from collections import deque
N,M = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x:x*(-1), a))
A = []

for a_ in a:
    heappush(A,a_) 

for _ in range(M):
  maxA = ceil(heappop(A)/2)
  A.append(maxA)
  
ans = sum(A)*-1
print(ans)
### BUGGY CODE ###

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

p_total = []
max_p_total = 0
ans = 0

for i in range(n - k +1):
    p_total.append(sum(p[i:i+k]))

max_p_total = max(p_total)
ans = (k + max_p_total)/2
print(ans)


### FIXED CODE ###

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

sum_p =[0]
tmp = 0
for i in p:
    tmp += i
    sum_p.append(tmp)

max_expect = 0
for i in range(k, n+1):
    tmp = sum_p[i] - sum_p[i - k]
    max_expect = max(tmp, max_expect)

ans = (k + max_expect)/2
print(ans)
### BUGGY CODE ###

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

d = dict()
for i in range(n):
    d[a[i]] = d.get(a[i], 0) + 1

d = sorted(d.values())
ans = 0
while k < len(d):
    ans += d.pop(0)

print(ans)

### FIXED CODE ###

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

d = dict()
for i in range(n):
    d[a[i]] = d.get(a[i], 0) + 1

d = sorted(d.values())
print(sum(d[:len(d)-k]))
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = [input() for i in range(n)]

d = Counter(s)

ma = [m[0] for m in d.items() if m[1] == max(d.values())]
print(*sorted(ma))

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for i in range(n)]

d = Counter(s).most_common()

s = d[0][1]
ans = []
for k, v in d:
    if s == v:
        ans.append(k)
    else:
        break
print(*sorted(ans), sep="\n")
### BUGGY CODE ###

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

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    temp = sorted(temp)
    if len(temp) > Q - 1:
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)

### FIXED CODE ###

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

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            if l >= K:
                temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    if l >= K:
        temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    if len(temp) > Q - 1:
        temp = sorted(temp)
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)
### BUGGY CODE ###

s = input()
q=int(input())

for i in range(q):
#     print(s)
    q_y_i = input().split()
#     print(q_y_i)
    if q_y_i[0] == '1':
        s = s[::-1]
    elif q_y_i[0] == '2':
        if q_y_i[1] == '1':
            s = q_y_i[2] + s
        elif q_y_i[1] == '2':
            s = s + q_y_i[2]
            
print(s)

### FIXED CODE ###

s = input()
q=int(input())

from collections import deque
d = deque()
d.append(s)

count = 1
for i in range(q):
#     print(s)
    q_y_i = input().split()
#     print(q_y_i)
#     print(count)
#     print(d)
    if q_y_i[0] == '1':
        count +=1
    else:
        if count % 2 == 1:
            if q_y_i[1] == '1':
                d.appendleft(q_y_i[2])
#                 print('p1')
#                 print(d)
            elif q_y_i[1] == '2':
                d.append(q_y_i[2])
#                 print('p2')
        elif count % 2 == 0:
            if q_y_i[1] == '1':
                d.append(q_y_i[2])
#                 print('p3')
            elif q_y_i[1] == '2':
                d.appendleft(q_y_i[2])
#                 print('p4')

ans = ''
for v in d:
    ans = ans + v
if count % 2 == 0:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

N ,K =(int(x) for x in input().split(' '))

s = 0

for a in range(K,N+2) :
  
  SUM1 = sum([x for x in range(0,a)])
  SUM2 = sum([x for x in range(N-a+1, N+1)])
  
  s = s + SUM2 - SUM1 + 1
  
print(s%(10**9+7))

### FIXED CODE ###

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

a = (n-k+2)*(((k+n+1)*(n+1))+2)//2
b = (((n+1)*(n+2)))*(2*n+3)//6
c = (((k-1)*k))*(2*k-1)//6

print((a-b+c)%(10**9+7))
### BUGGY CODE ###

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

def gcd(a, b):
  if b == 0:
    return a
  else:
    return gcd(b, a%b)
def gcd_array(a):#aは配列
  return reduce(gcd, a)

ans = []
lst_l = [lst[0]]
lst_r = [lst[n-1]]
for i in range(n-1):
  lst_l.append(gcd(lst_l[-1], lst[i + 1]))
  lst_r.insert(0, gcd(lst_r[0], lst[n-2-i]))

ans.append(lst_r[1])
for i in range(n-2):
  ans.append(gcd(lst_l[i], lst_r[i+2]))
ans.append(lst_l[-2])

print(max(ans))

### FIXED CODE ###

import fractions

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

ans = 0
left = [0]
right = [0] * (n+1)

for i in range(n):
  left.append(fractions.gcd(left[-1],lst[i]))
  right[n-1-i] = fractions.gcd(right[n-i],lst[n-1-i])

for i in range(n):
  x = fractions.gcd(left[i], right[i+1])
  if ans < x:
    ans = x
print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

def solve(uf, first_order_friends, blocked_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(list(set(uf.members(i)) - first_order_friends[i] - blocked_list[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        blocked_list[c].add(d)
        blocked_list[d].add(c)

    for ans in solve(uf, first_order_friends, blocked_list)[1:]:
        print(ans, end=' ')

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

def solve(uf, except_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(uf.size(i) - 1 - len(except_list[i]))
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    except_list = [[] for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        except_list[a].append(b)
        except_list[b].append(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        if not uf.same(c, d):
            continue
        except_list[c].append(d)
        except_list[d].append(c)

    for ans in solve(uf, except_list)[1:]:
        print(ans, end=' ')
### BUGGY CODE ###

N,M = map(int,input().split())
AB = []
ans = 0
for i in range(N):
    A,B = map(int,input().split())
    t = A,B
    AB.append(t)
    
AB.sort()

for i in range(len(AB)):
    for x in range(AB[i][1]):
        if M > 0:
            ans += AB[i][0]
            M -= 1
        

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M=[int(x) for x in input().strip().split()]
AN=[]
BN=[]
val={}
for i in range(N):
    Ai,Bi=[int(x) for x in input().strip().split()]
    val[Ai]=Bi+val.get(Ai,0)
    AN.append(Ai)
 
AN=sorted(set(AN))
m=0
ans=0
for Ai in AN:
    ans+=Ai*min(M-m,val[Ai])
    m+=min(M-m,val[Ai])
    if m==M:
        break
print(ans)
### BUGGY CODE ###

def main():
  h,n = [int(i) for i in input().split()]
  ab = []
  for i in range(n):
    a,b = [int(i) for i in input().split()]
    ab.append([a,b])
  dp = [[10**8]*((h+1)+10**4) for i in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(h+1+10**4):
      if j>=ab[i][0]:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-ab[i][0]]+ab[i][1])
      else:
        dp[i+1][j]=dp[i][j]

  ans = 10**8    
  for i in range(n+1):
    for j in range(h,h+1+10**4):
      ans = min(ans,dp[i][j])
  print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

h,n = [int(i) for i in input().split()]
ab = []
for i in range(n):
  a,b = [int(i) for i in input().split()]
  ab.append([a,b])
dp = [[10**8]*((h+1)+10**4) for i in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(h+1+10**4):
    if j>=ab[i][0]:
      dp[i+1][j]=min(dp[i][j],dp[i+1][j-ab[i][0]]+ab[i][1])
    else:
      dp[i+1][j]=dp[i][j]
      
ans = 10**8    
for i in range(n+1):
  for j in range(h,h+1+10**4):
    ans = min(ans,dp[i][j])
print(ans)
### BUGGY CODE ###

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

dp = [True] * (A[-1] + 1)
for a in A:
    if dp[a] == True:
        n = 2
        while n * a <= A[-1]:
            dp[n * a] = False
            n += 1

score = 0
for a in A:
    score += dp[a] * (A.count(a) == 1)
    
print(score)

### FIXED CODE ###

import collections

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

dp = collections.defaultdict(lambda: True)

for i in range(N):
    if i < N - 1 and A[i] == A[i + 1]:
        dp[A[i]] = False
    k = 2
    while True:
        if A[i] * k > A[-1]:
            break
        else:
            dp[A[i] * k] = False
            k += 1

print(sum(dp[a] for a in A))
### BUGGY CODE ###

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

dic = []
count = 0
for x in a:
    if x not in dic:
        dic.append(x)
        if a.count(x) > x:
            count+= a.count(x) - x
        elif a.count(x) < x:
            count += a.count(x)
print(count)

### FIXED CODE ###

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


count = len([i for i in a if i > 10**5])
a = [e for e in a if e <= 10**5]
dic = list(set(a))
for x in dic:
    if a.count(x) > x:
        count+= a.count(x) - x
    elif a.count(x) < x:
        count += a.count(x)
print(count)
### BUGGY CODE ###

import numpy as np
def so(n):
    for i in range(3, int(np.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True
A, B = map(int, input().split())
M = np.min([A, B])
n = 1
if (A % 2 == 0) and (B % 2 == 0):
    n = 2
for i in range(3, M, 2):
    if so(i):
        if (A % i == 0) and (B % i == 0):
            n = n + 1
print(n)


### FIXED CODE ###

import numpy as np
def p(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
A, B = map(int, input().split())
M = np.min([A, B])
a = p(A)
b = p(B)
t = set(a) & set(b)
print(len(t) + 1)
### BUGGY CODE ###

import numpy as np
import collections
n = int(input())
a = np.array(list(map(int, input().split())))
check = np.arange(1, n+1)
c = list(a - check)
b = collections.Counter(c)
b = np.array(list(b.keys()))
count = 0
for i in range(1, n+1):
    count += abs(a[i-1] - i - b)
print(min(count))


### FIXED CODE ###

import numpy as np
n = int(input())
if n == 1:
    a = input()
    print(0)
else:
    a = np.array(list(map(int, input().split())))
    check = np.arange(1, n+1)
    c = sorted(list(a - check))
    b1 = c[int(n/2)]
    b2 = c[int(n/2)+1]
    count1 = 0
    count2 = 0
    for i in range(1, n+1):
        count1 += abs(a[i-1] - i - b1)
        count2 += abs(a[i-1] - i - b2)
    print(min(count1, count2))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
s = [input() for _ in range(H)]

d = [[-1]*W for _ in range(H)]

que = deque([[cw, ch, 0]])
while que:
    x, y, cost = que.popleft()
    if d[y][x]==-1 or d[y][x]>cost:
        d[y][x] = cost
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and s[ny][nx]!='#':
                    if abs(dx)+abs(dy) == 1:
                        que.append([nx, ny, cost])
                    else:
                        que.append([nx, ny, cost+1])  
print(d[dh][dw])



### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch-1, cw-1, dh-1, dw-1
s = [input() for _ in range(H)]

d = [[-1]*W for _ in range(H)]

que = deque([[cw, ch, 0]])
while que:
    x, y, cost = que.popleft()
    if d[y][x]==-1 or d[y][x]>cost:
        d[y][x] = cost
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x+dx, y+dy
                if 0<=nx<W and 0<=ny<H and s[ny][nx]!='#':
                    if abs(dx)+abs(dy) == 1:
                        que.appendleft([nx, ny, cost])
                    else:
                        que.append([nx, ny, cost+1])  
print(d[dh][dw])
### BUGGY CODE ###

def triplets_brute(n):
    counter = 0
    upper = round(n**0.5)
    for x in range(1, upper+1):
        for y in range(1, upper+1):
            for z in range(1, upper+1):
                if x**2+y**2+z**2+x*y+y*z+z*x==n:
                    counter += 1
    return counter
for m in range(1, int(input())+1):
	print(triplets_brute(m))

### FIXED CODE ###

N = int(input())
l = [0]*N
upper = round((N-1)**0.5-1)
for x in range(1, upper+1):
    for y in range(1, upper + 1):
        for z in range(1, upper + 1):
            tmp = x**2+y**2+z**2+x*y+y*z+z*x
            if tmp < N+1:
                l[tmp-1]+=1
for x in l:
    print(x)
### BUGGY CODE ###


#約数リスト
import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P




def resolve():
    n = int(input())
    A = get_primes(int(1.2*n))

    for i in A:
        if i>=n:
            print(i)
            return





if __name__ == "__main__":
    resolve()

### FIXED CODE ###




#約数リスト
import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P




def resolve():
    n = int(input())
    A = get_primes(int(1.2*n))

    for i in A:
        if i>=n:
            print(i)
            return





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

import sys
from itertools import permutations
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XY = np.array([list(map(int, readline().split())) for _ in range(N)])

dist = 0
cnt = 0
for route in permutations(XY, N):
    acc = 0
    for i in range(N - 1):
        acc += np.sqrt(sum(pow(route[i] - route[i + 1], 2)))
    dist += acc
    cnt += 1
print(dist / cnt)

### FIXED CODE ###

import sys
from itertools import permutations
from math import factorial
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
XY = [list(map(int, readline().split())) for _ in range(N)]

dist = 0
for route in permutations(XY, N):
    acc = 0
    dists = [
        np.sqrt(
            pow(route[i][0] - route[i + 1][0], 2) +
            pow(route[i][1] - route[i + 1][1], 2)) for i in range(N - 1)
    ]
    dist += sum(dists)
print(dist / factorial(N))
### BUGGY CODE ###

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

a.sort()
f.sort(reverse=True)

l = -1
r = 10**12

while l+1 < r:
  c = (l+r)//2
  s = 0
  for i in range(n):
    s += max(0, a[i] - c//f[i])
  if s <= k:
    r = c
  else:
    l = c
print(r)


### FIXED CODE ###

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

a.sort()
f.sort(reverse=True)

l = -1
r = 10**12

while l+1 < r:
  c = (l+r)//2
  s = 0
  for i in range(n):
    s += max(0, a[i] - c//f[i])
  if s <= k:
    r = c
  else:
    l = c
print(r)
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

T = defaultdict(list)
for i in range(N-1):
    x,y = map(int, input().split())
    T[x] += [y]
    T[y] += [x]

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD) 



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

# T = defaultdict(list)
T = [set() for _ in range(N+1)]
for i in range(N-1):
    x,y = map(int, input().split())
    # T[x] += [y]
    # T[y] += [x]
    T[x].add(y)
    T[y].add(x)

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

for i in range(1,N+1):
    print(A.index(i)+1)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
L = [[] for i in range(N)]
for i in range(N):
    L[i] = [A[i], i+1]
L = sorted(L)
for i in range(N):
    print(L[i][1])
### BUGGY CODE ###

from collections import Counter
N = int(input())
A_list = list(map(int, input().split()))
A_list_max  = max(A_list)
C = Counter(A_list)

cnt = 0
A_baisu = []

for i in range(N):
    k = A_list_max//A_list[i]
    #print(k, A_list_max)
    if C[A_list[i]] >= 2:
        A_baisu.append(A_list[i])
    if k >= 2:
        for j in range(2, k+1):
            if A_list[i]*j in A_list:
                A_baisu.append(A_list[i]*j)

A_baisu = list(set(A_baisu))
#print(A_baisu)

for i in range(len(A_baisu)):
    cnt += A_list.count(A_baisu[i])
ans = N - cnt

print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)