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

from math import gcd

def euler_phi(n):
    res=n
    for x in range(2,int(n**.5)+2):
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res


def biggcd(n,m):
    g=gcd(n,m)
    res=g
    count=2
    while True:
        test=gcd(g**count,m)
        if test>res:
            res=test
            count+=1
        else:
            break
    return res


def solve(a,m,n):
    #print(a,m,n)
    if gcd(a,m)==1:
        if m==1:
            return 1
        phi=euler_phi(m)
        G=gcd(phi,m)
        r0=solve(a,G,n)
        return (((pow(a,n*r0)-n*r0)//G)*pow(n*phi//G,phi-1,m)*phi+r0)%(m*phi//G)
    else:
        big=biggcd(a,m)
        k0=solve(a,m//big,n*big)
        return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))
    #ans=solve(A,M,1)
    #print(pow(A,ans,M)%M==ans%M)


### FIXED CODE ###

from math import gcd

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime=get_sieve_of_eratosthenes_new(32000)

def euler_phi(n):
    res=n
    for x in prime:
        if n%x==0:
            res=(res//x)*(x-1)
            while n%x==0:
                n//=x
    if n!=1:
        res=(res//n)*(n-1)
    return res


def biggcd(n,m):
    g=gcd(n,m)
    res=g
    count=2
    while True:
        test=gcd(g**count,m)
        if test>res:
            res=test
            count+=1
        else:
            break
    return res


def solve(a,m,n):
    #print(a,m,n)
    if gcd(a,m)==1:
        if m==1:
            return 1
        phi=euler_phi(m)
        G=gcd(phi,m)
        r0=solve(a,G,n)
        mod=m*phi//G
        return ((((pow(a,n*r0,mod)-n*r0)%mod)//G)*pow(n*phi//G,phi-1,m)*phi+r0)%mod
    else:
        big=biggcd(a,m)
        k0=solve(a,m//big,n*big)
        return big*k0

for i in range(int(input())):
    A,M=map(int,input().split())
    print(solve(A,M,1))
    #ans=solve(A,M,1)
    #print(pow(A,ans,M)%M==ans%M)
### BUGGY CODE ###

import sys
from itertools import accumulate


def E(i, x):
    if i == 1:
        return 5 * x
    return (2 * i + 1) * x


N, X = map(int, input().split())
x = list(map(int, input().split()))
x.sort(key=None, reverse=True)
x = list(accumulate(x))
x.insert(0, 0)
energy = sys.maxsize
for k in range(1, N + 1):
    cost = 0
    for i in range(1, N + 1):
        if i * k <= N:
            cost += E(i, x[i * k] - x[(i - 1) * k])
        else:
            cost += E(i, x[-1] - x[(i - 1) * k])
            break
    energy = min(energy, cost + (N + k) * X)
print(energy)


### FIXED CODE ###

from itertools import accumulate
def E(i, x):
    if i == 1:
        return 5 * x
    return (2 * i + 1) * x
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.sort(key=None, reverse=True)
x = list(accumulate(x))
x.insert(0, 0)
energy = 9223372036854775807
for k in range(1, N + 1):
    cost = (N + k) * X
    for i in range(1, N + 1):
        if i * k <= N:
            cost += E(i, x[i * k] - x[(i - 1) * k])
        else:
            cost += E(i, x[-1] - x[(i - 1) * k])
            break
    if cost < energy:
        energy = cost
print(energy)
### BUGGY CODE ###

n, ma, mb = map(int,input().split())
a = [0] * (n + 1)
b = [0] * (n + 1)
c = [0] * (n + 1)
for i in range(1, n + 1):
    a[i], b[i], c[i] = map(int,input().split())

#iまでの薬品で、aがj(g),bがk(g)となるときの最小コスト
dp = [[[10 ** 15 for i in range(n + 1)] for j in range(401)] \
    for k in range(401)]

dp[0][0][0] = 0

for i in range(1, n + 1):
    for j in range(401):
        for k in range(401):
            if j < a[i] or k < b[i]:
                dp[k][j][i] = dp[k][j][i - 1]
            else:
                dp[k][j][i] = min(dp[k][j][i - 1], \
                    dp[k - b[i]][j - a[i]][i - 1] + c[i])

i = 1
ans = 10 ** 15
while True:
    if i * ma > 400 or i * mb > 400:
        break
    ans = min(ans, dp[i * mb][i * ma][n])
    i += 1

if ans == 10 ** 15:
    ans = -1

print(ans)

### FIXED CODE ###

import fractions

n, ma, mb = map(int,input().split())
a = [0] * (n + 1)
b = [0] * (n + 1)
c = [0] * (n + 1)
for i in range(1, n + 1):
    a[i], b[i], c[i] = map(int,input().split())

#iまでの薬品で、aがj(g),bがk(g)となるときの最小コスト
dp = [[[10**15 for i in range(n + 1)] for j in range(401)] \
    for k in range(401)]

dp[0][0][0] = 0
sa = [0] * (n + 1)
sb = [0] * (n + 1)

for i in range(1, n + 1):
    sa[i] = sa[i - 1] + a[i]
    sb[i] = sb[i - 1] + b[i]

for i in range(1, n + 1):
    for j in range(401):
        if j > sa[i]:
            break
        for k in range(401):
            if k > sb[i]:
                break
            # i番目を買うか、買わないか
            if j < a[i] or k < b[i]:
                dp[k][j][i] = dp[k][j][i - 1]
            else:
                dp[k][j][i] = min(dp[k][j][i - 1], \
                    dp[k - b[i]][j - a[i]][i - 1] + c[i])

i = 1
ans = 10 ** 15
while True:
    if i * ma > 400 or i * mb > 400:
        break
    ans = min(ans, dp[i * mb][i * ma][n])
    i += 1

if ans == 10 ** 15:
    ans = -1

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

n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].extend(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].extend(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))))
print(" ".join(ans))

### FIXED CODE ###

n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[{i} for i in range(n)]
rail=[{i} for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].add(q)
    road[q].add(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].add(s)
    rail[s].add(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(road[tmp])
        road[i].update(road[tmp])
    for j in road[i]:
        road[j]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        d.extend(rail[tmp])
        rail[i].update(rail[tmp])
    for j in rail[i]:
        rail[j]=rail[i]
ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    sumset=road[i]&rail[i]
    for j in sumset:
        ans[j]=str(len(sumset))
print(" ".join(ans))
### BUGGY CODE ###

import numpy as np
N, K=map(int, input().split())
Q=list(map(int, input().split()))
P=np.array([Q[i:i+K] for i in range(N-K+1)])

best=(P.sum(axis=1)).max()

"""
best=0

for i in range(N-K+1):
  point=P[i:i+K].sum()
  
  if point>best:
    best=point
"""  
    


print(best/2+K/2)



### FIXED CODE ###

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

#n面サイコロの出る目の期待値
def n_mean(n):
  return 0.5*(n+1)

Pmean=list(map(lambda x: n_mean(x), P))
Psum=[0]*N
Psum[0]=Pmean[0]
for i in range(1,N):
  Psum[i]=Psum[i-1]+Pmean[i]
#print(Psum)
ans=0
for i in range(N-K+1):
  if i==0:
    ans=Psum[K-1]
  else:
    #1~6 
    ans=max(ans, (Psum[i+K-1]-Psum[i-1]))
  
print(ans)
### BUGGY CODE ###

n = int(input())
lst = list(map(int, input().split()))
lst2 =[]
maxval2 = 0
flag = 0
maxval = max(lst)
for _ in range(n-1):
  lst.pop(lst.index(maxval))
  maxval2 = max(lst)
  if maxval == maxval2:
    print('NO')
    flag = 1
    break
  maxval = maxval2
if flag == 0:
  print('YES')


### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
flag = 0
lst.sort()
for i in range(n-1):
  if lst[i] == lst[i+1]:
    print('NO')
    flag = 1
    break
if flag == 0:
  print('YES')
### BUGGY CODE ###

from collections import defaultdict

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
    
  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      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 size(self, x):
    return -self.parents[self.find(x)]

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

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

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
  
uf = UnionFind(n)
for a, b in AB:
  a -= 1
  b -= 1
  uf.union(a, b)

ans = 0
for _, v in uf.all_group_members().items():
  ans = max(ans, len(v))
  
print(ans)

### FIXED CODE ###

from collections import defaultdict

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
    
  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      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 size(self, x):
    return -self.parents[self.find(x)]

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

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

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
  
uf = UnionFind(n)
for a, b in AB:
  a -= 1
  b -= 1
  uf.union(a, b)

ans = 0
for v in uf.roots():
  ans = max(ans, uf.size(v))
  
print(ans)
### BUGGY CODE ###

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        m2 = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            m = m+b
            M = [[jj for jj in ii] for ii in m]
            x = min(r+1, 64)
            newr = x
            for ii in range(x):
                if M[ii][ii] == 0:
                    for jj in range(ii+1, r+1):
                        if M[jj][ii]:
                            for kk in range(ii, 64):
                                M[ii][kk] ^= M[jj][kk]
                            break
                    else:
                        for jj in range(ii+1, 64):
                            if M[ii][jj] != 0:
                                for kk in range(ii, r+1):
                                    M[kk][ii] ^= M[kk][jj]
                                break
                        else:
                            newr -= 1
                M2 = M[ii]
                for jj in range(ii+1, r+1):
                    M3 = M[jj][ii]
                    M[jj][ii] = 0
                    for kk in range(ii+1, 64):
                        M[jj][kk] ^= M3*M2[kk]
            if s[i] == "0":
                if newr > r:
                    r += 1
                else:
                    m.pop()
            else:
                m.pop()
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()


### FIXED CODE ###

def main():
    t = int(input())
    for _ in range(t):
        nn, aa, s, r, mm = int(input()), list(map(int, input().split())), input(), 0, []
        for ii in range(nn-1, -1, -1):
            ai = aa[ii]
            mm += [[(ai >> jj) & 1 for jj in range(64)]]
            n, i, j = r+1, 0, 0
            while i < n and j < 64:
                if mm[i][j] == 1 and mm[n-1][j] == 0:
                    i += 1
                    j += 1
                    continue
                if mm[i][j] == 0:
                    if mm[n-1][j] != 0:
                        for l in range(j, 64):
                            mm[i][l] ^= mm[n-1][l]
                    else:
                        j += 1
                        continue
                M2 = mm[i]
                for k in range(i+1, n):
                    M3 = mm[k][j]
                    mm[k][j] = 0
                    for l in range(j+1, 64):
                        mm[k][l] ^= M3*M2[l]
                i += 1
                j += 1
    
            if s[ii] == "0":
                if i > r:
                    r += 1
                else:
                    mm.pop()
            else:
                mm.pop()
                if i > r:
                    print(1)
                    break
        else:
            print(0)


main()
### BUGGY CODE ###

N = int(input())
S = input()
l = [i for i in S]
ew = [0]
ans = min(l.count("W"),l.count("E"))

i = 0
while True:
    num = S.find("EW",i+1)
    if num != -1:
      ew.append(num)
      i = num
    else:
      break
      
for i in ew:
  ans = min(ans,l[:i+1].count("W") + l[i+1:].count("E"))

print(ans)

### FIXED CODE ###

N = int(input())
S = [i for i in input()]
ans = S.count("E")
cnt = S.count("E")

for i in S:
  if i == "W":
    cnt += 1
  elif i == "E":
    cnt -= 1
    ans = min(ans,cnt)
  
print(ans)
### BUGGY CODE ###

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

# a1,...,anのgcdをDと仮定
# M >= N*D が成立
# Dの候補が絞れる

D = []
d = 1
while M >= N * d:
	D.append(d)
	d += 1

maxg = 1
for d in D:
	if (M - d * (N - 1)) % d == 0:
		maxg = max(maxg, d)

print(maxg)

### FIXED CODE ###

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

def divisible(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

div = divisible(M)

div = [d for d in div if d <= M / N]

print(max(div))
### BUGGY CODE ###

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

for i in range(1,n+1):
	nums.append(a.count(i))

for i in nums:
	print(i)

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
subs = [0] * N

for boss in A:
  subs[boss-1] += 1

for i in subs:
  print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N,M,Q = map(int,input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
    a[i],b[i],c[i],d[i] = map(int,input().split())


sequences = []
def dfs(s):
    if len(s) == N:
        sequences.append(s)
        return
    if s == '':
        tail_num = 1
    else:
        tail_num = int(s[-1])
    for nxt_d in range(tail_num,M+1):
        dfs(s+str(nxt_d))
dfs('')

ans = 0
for seq in sequences:
    score = 0
    for i in range(Q):
        if int(seq[b[i] - 1]) - int(seq[a[i] - 1]) == c[i]:
            score += d[i]
    ans = max(ans, score)
print(ans)




### FIXED CODE ###

N,M,Q = map(int,input().split())
a = [0]*Q
b = [0]*Q
c = [0]*Q
d = [0]*Q
for i in range(Q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
import itertools
ans = 0
for seq in itertools.combinations_with_replacement(range(1,M+1),N):
    score = 0
    for i in range(Q):
        if seq[b[i]-1] - seq[a[i]-1] == c[i]:
            score += d[i]
    ans = max(ans,score)
print(ans)
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h

for i in range(h):
  grid[i]=input()

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  s=grid[i]
  left=0
  right=0
  while left<len(s):
    if s[left]=="#":
      left+=1
      right=left
      continue
    while right+1<w and s[right+1]==".":
      right+=1
  
    for j in range(left,right+1):
      yoko[i][j]=right-left
      
    left=right+1
    right=left
    
for i in range(w):
  up=0
  down=0
  while up<h:
    if grid[down][i]=="#":
      up+=1
      down=up
      continue
    while down+1<h and grid[down+1][i]==".":
      down+=1
    for j in range(up,down+1):
      tate[j][i]=down-up
    up=down+1
    down=up
    
ans=0
for i in range(h):
  for j in range(w):
    if grid[i][j]==".":
      ans=max(ans,tate[i][j]+yoko[i][j])
      
print(ans+1)


### FIXED CODE ###

h,w=map(int,input().split())
grid=[None]*h

for i in range(h):
  grid[i]=input()

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  s=grid[i]
  left=0
  right=0
  while left<len(s):
    if s[left]=="#":
      left+=1
      right=left
      continue
    while right+1<w and s[right+1]==".":
      right+=1
  
    for j in range(left,right+1):
      yoko[i][j]=right-left
      
    left=right+1
    right=left
    
for i in range(w):
  up=0
  down=0
  while up<h:
    if grid[down][i]=="#":
      up+=1
      down=up
      continue
    while down+1<h and grid[down+1][i]==".":
      down+=1
    for j in range(up,down+1):
      tate[j][i]=down-up
    up=down+1
    down=up
    
ans=0
for i in range(h):
  for j in range(w):
    if grid[i][j]==".":
      ans=max(ans,tate[i][j]+yoko[i][j])
      
print(ans+1)
### BUGGY CODE ###

 # -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

def main():
	N, W = map(int, input().split(" "))
	goods = []
	for _ in range(N):
		w, v = map(int, input().split(" "))
		goods.append((w, v))
		
	DP = [[0] * (W+2) for _ in range(N+1)]
	for i in range(N):
		w, v = goods[i]
		for w_sum in range(W+1):
			DP[i+1][w_sum] = max(DP[i+1][w_sum], DP[i][w_sum])
			if w_sum - w >= 0:
				DP[i+1][w_sum] = max(DP[i+1][w_sum], DP[i][w_sum - w] + v)
		
	print(DP[N][W])
		
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		if w <= W:
			wv.append((w,v))
		
	DP = [[0 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][w] = v
			continue
			
		for j in range(W):
			DP[i][j] = max(DP[i-1][j], DP[i][j])
			
			if j+w <= W:
				DP[i][j+w] = max(DP[i-1][j] + v, DP[i][j+w])
			
	print(max(DP[N-1]))
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

x,y,z,n = map(int, input().split())
a = sorted(list(map(int, input().split())),reverse = True)
b = sorted(list(map(int, input().split())),reverse = True)
c = sorted(list(map(int, input().split())),reverse = True)
d = []
for i,i1 in enumerate(a):
  for j,j1 in enumerate(b[:n // (i+1)]):
    for k,k1 in enumerate(c[:n // (i+1) * (j+1)]):
        d.append(i1 + j1 + k1)

d.sort(reverse = True)
for i in d[:n]:
  print(i)


### FIXED CODE ###

x,y,z,n = map(int, input().split())
a = sorted(list(map(int, input().split())),reverse = True)
b = sorted(list(map(int, input().split())),reverse = True)
c = sorted(list(map(int, input().split())),reverse = True)
d = []
for i,i1 in enumerate(a):
  for j,j1 in enumerate(b):
    if (i+1)*(j+1) <= n:
      for k,k1 in enumerate(c):
        if (i+1) * (j+1) * (k+1) <= n:
          d.append(i1 + j1 + k1)
        else:
          break
    else:
      break
d.sort(reverse = True)
for i in d[:n]:
  print(i)
### BUGGY CODE ###

N = int(input())

edges = {}

for _ in range(N-1):
    a, b, c = map(int, input().split())

    edges[(a, b)] = c
    edges[(b, a)] = c

Q, K = map(int, input().split())
xy = []
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))


d = [10**14] * (N+1)
d[K] = 0

for n in range(N):
    for e in edges:
        if d[e[0]] > d[e[1]] + edges[e]:
            d[e[0]] = d[e[1]] + edges[e]


for x, y in xy:
    print(d[x] + d[y])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100005)

N = int(input())

edges = {n: [] for n in range(N+1)}

for _ in range(N-1):
    a, b, c = map(int, input().split())

    edges[a].append((b, c))
    edges[b].append((a, c))

Q, K = map(int, input().split())
xy = []
for _ in range(Q):
    xy.append(tuple(map(int, input().split())))


d = [-1] * (N+1)
d[K] = 0


def dfs(n: int):
    for m, c in edges[n]:
        if d[m] == -1:
            d[m] = d[n] + c
            dfs(m)


dfs(K)

for x, y in xy:
    print(d[x] + d[y])
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(N):
    flag = 0
    for j in range(N):
        if i!=j and A[i]%A[j] == 0:
            #print("i=%d,j=%d,A[j]=%d"%(i,j,A[j]))
            flag +=1
    if flag == 0:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
D = set() #重複
S = set() #初出
for i in range(N):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])
#print(D,S)
M = max(S)
#print(M)
X = [1 for i in range(M+1)] #i番目が数字iに対応、条件を満たせば1、満たさなければ0にする。
#print(X)
for a in S:
    if a in D:
        X[a]=0 #aが重複していれば、aは条件を満たす数字ではない。
    for i in range(2*a,M+1,a):
        X[i]=0 #aはおｋ、2a以上のaの倍数は条件を満たさない。
        
ans = 0
for i in range(N):
    if X[A[i]]==1: #数字A(i)に対応するX[i]の箇所を参照して、条件を満たしていれば+1する
        ans += 1
print(ans)