Harryxun/stf_run huggingface dataset:
import numpy as np
import sys
input = sys.stdin.readline


max_size = 10**4 + 2 * 10**3
h, n = map(int, input().split())
DP = np.ones(max_size, dtype=np.int64) * 10**9
DP[0] = 0

for _ in range(n):
    power, cost = map(int, input().split())
    for i in range((h+power-1)//power):
        np.minimum(DP[(i+1)*power: (i+2)*power], DP[(i)*power: (i+1)*power] + cost, DP[(i+1)*power: (i+2)*power])

print(DP[h:].min())

### FIXED CODE ###

import sys
input = sys.stdin.readline

max_size = 2*10**4 + 1
h, n = map(int, input().split())
DP = [float('INF')] * max_size
DP[0] = 0

for _ in range(n):
    damage, cost = map(int, input().split())
    for idx in range(damage, max_size):
        DP[idx] = min(DP[idx], DP[idx-damage] + cost)

print(min(DP[h:]))
s = input()
ans = []
a = 0
for i in range(len(s)):
    if s[i] == "A":
        a += 1
    elif s[i] == "C":
        a += 1
    elif s[i] == "G":
        a += 1
    elif s[i] == "T":
        a += 1
    else:
        ans.append(a)
        a = 0
print(max(ans))

### FIXED CODE ###

s = input()
ans = [0]
for i in range(len(s)):
    if s[i] == "A":
        ans[-1] += 1
    elif s[i] == "C":
        ans[-1] += 1
    elif s[i] == "G":
        ans[-1] += 1
    elif s[i] == "T":
        ans[-1] += 1
    else:
        ans.append(0)
print(max(ans))
N, C, K = [int(i) for i in input().split()]
T = sorted([int(input())] for i in range(N))
ans = 1
limit = 0
ti = T[0]
for i in range(N - 1):
    limit += 1
    if ti + K < T[i + 1] or limit == C:
        ti = T[i + 1]
        ans += 1
        limit = 0
print(ans)


### FIXED CODE ###

N, C, K = [int(i) for i in input().split()]
T = sorted([int(input()) for i in range(N)])
ans = 1
limit = 0
ti = T[0]
for i in range(N - 1):
    limit += 1
    if ti + K < T[i + 1] or limit == C:
        ti = T[i + 1]
        ans += 1
        limit = 0
print(ans)
# -*- coding: utf-8 -*-


int a,b=map(input().split())


s=0.5*(a+b)

int v= int(s)+1

print(v)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Nov  3 09:19:07 2018

@author: sk
"""

     
      
b, c = map(int, input().split())
     
s=0.5*(b+c)
     
d = int(s)
    
if s-d > 0:
    v=int(d+1)
else :
    v=int(d)
print(v)
import math

N = int(input())

a = math.floor(n / 1.08)
b = a + 1

aa = math.floor(a * 1.08)
bb = math.floor(b * 1.08)

if(aa == N):
    print(aa)
elif(bb == N):
    print(bb)
else:
    print(":(")

### FIXED CODE ###

import math

N = int(input())

a = math.floor(N / 1.08)
b = a + 1

aa = math.floor(a * 1.08)
bb = math.floor(b * 1.08)

if(aa == N):
    print(a)
else:
    if(bb == N):
        print(b)
    else:
        print(":(")
import math

a,b,c,d = map(int,input().split())
tn = b-a+1

cn = (b//c)-((a-1)//c)
dn = (b//d)-((a-1)//d)
cd = (c * d) // math.gcd(c, d)
cdn = (b//cd)-((a-1)//cd)

print(tn-cn-dn+cdn)

### FIXED CODE ###

import fractions

a,b,c,d = map(int,input().split())
tn = b-a+1

cn = (b//c)-(a-1)//c
dn = (b//d)-(a-1)//d
cd = (c*d)//fractions.gcd(c, d)
cdn = (b//cd)-(a-1)//cd

print(tn-cn-dn+cdn)
if S > W:
  print('safe')
else:
  print('unsafe')

### FIXED CODE ###

S, W = input().split()

S = int(S)
W = int(W)

if S <= W:
    print('unsafe')
else:
    print('safe')
o=input()
e=input()
s=""
for i in range(len(o)):
  if not e[i]:
    s+=o[i]+e[i]
  else:
    s+=o[i]
print(s)

### FIXED CODE ###

o=input()
e=input()
s=""
for i in range(len(o)):
  if len(e) == i:
    s+=o[i]
  else:
    s+=o[i]+e[i]
print(s)
# B - Power Socket

a = int(input())
b = int(input())
div = b // (a - 1)
mod = b % (a - 1)

print(1 if a == b else (div + 1 if mod > 1 else div))

### FIXED CODE ###

# B - Power Socket

a, b = list(map(int, input().split()))
tgt = b - a

if tgt == 0:
    print(1)
else:
    div = tgt // (a - 1)
    mod = tgt % (a - 1)
    print(div + 2 if mod > 0 else div + 1)
X = list(map(int,input().split()))

if X[0]==0:
  print(1)
 elif X[1] == 0:
    print(2)
 elif X[2] == 0:
    print(3)
 elif X[3] == 0:
    print(4)
 else:
    print(5)


### FIXED CODE ###

X = list(map(int,input().split()))

if X[0]==0:
  print(1)
elif X[1] == 0:
  print(2)
elif X[2] == 0:
  print(3)
elif X[3] == 0:
  print(4)
else:
  print(5)
A1, A2, A3 = map(int, input().split())
if A1 + A2 + A3 >= 22:
  print('bust')
else;
  print('win')


### FIXED CODE ###

a1, a2, a3 = map(int, input().split())
if a1 + a2 + a3 >= 22:
    print('bust')
else:
    print('win')
lst = list(int, input().split())

if (lst[0] < lst[1]):
  print(0)
else:
  print(10)

### FIXED CODE ###

lst = list(map(int, input().split()))
 
if (lst[0] < lst[1]):
  print(0)
else:
  print(10)
from math import ceil
N,K = map(int,input().split())
A=list(map(int,input().split()))


low=0
high=10**9+1

while low<=high:
    #答え(全てをmid以下の長さにできるならOK)
    mid=(low+high)//2
    cnt=0
    for a in A:
        v=ceil(a/mid)
        cnt+=max(v-1,0)

    if cnt<=K:
        high=mid-1
    else:
        low=mid+1
print(low)


### FIXED CODE ###

from math import ceil
N,K = map(int,input().split())
A=list(map(int,input().split()))


low=0
high=10**9+1

while low<=high:
    mid=(low+high)//2
    if mid==0:
        print(1)
        exit()

    cnt=0
    for a in A:
        if a<=mid:
            continue
        v=ceil(a/mid)
        cnt+=v-1

    if cnt<=K:
        high=mid-1
    else:
        low=mid+1
print(low)
def f(n):
  cnt = 0
  while n:
      cnt += 1
      n = n % bin(n).count('1')

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1)

  for i, s in enumerate(src):
    i = n - 1 - i
    num = None

    if s == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()


### FIXED CODE ###


def f(n):
  cnt = 0
  while n:
      cnt += 1
      n = n % bin(n).count('1')

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1) if base_cnt > 1 else 0

  for i, s in enumerate(src):
    i = n - 1 - i
    num = None

    if s == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
H, W = read_int()

range_W = range(W)
range_H = range(H)
# nomal
L = [[0 for _ in range_W] for _ in range_H]
R = [[0 for _ in range_W] for _ in range_H]
U = [[0 for _ in range_W] for _ in range_H]
D = [[0 for _ in range_W] for _ in range_H]
res = [[0 for _ in range_W] for _ in range_H]
grid = []

append = grid.append
for i in range_H:
    row = list(" ".join(input()).split())
    append(row)

def solve():
    ans = 0
    for i in range_H:
        for j in range_W:
            if grid[i][j] == ".":
                L[i][j] = 1 if j == 0 else L[i][j - 1] + 1
                U[i][j] = 1 if i == 0 else U[i - 1][j] + 1
                res[i][j] += L[i][j] + U[i][j]
                ans = max(res[i][j], ans)

            if grid[H - i - 1][W - j - 1] == ".":
                R[H - i - 1][W - j - 1] = 1 if j == 0 else R[H - i - 1][W - j] + 1
                D[H - i - 1][W - j - 1] = 1 if i == 0 else D[H - i][W - j - 1] + 1
                res[H - i - 1][W - j - 1] += R[H - i - 1][W - j - 1] + D[H - i - 1][W - j - 1]
                ans = max(res[H - i - 1][W - j - 1], ans)
    return ans - 3

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


### FIXED CODE ###

from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

P = read_int()
P.sort()
def solve():
    return P[0] + P[1]

if __name__ == "__main__":
    print(solve())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = []
d = []
for i in range(a[0]):
	c.append(abs(b[i]-a[1]))
	if b[i]-a[1] > 0:
		c.insert(i,0)

for i in range(len(c)-1):
	d.append(abs(c[i+1]-c[i]))
	if d[-1] == 0:
		d.pop()
d.sort()
for i in range(len(d)-1):
	if d[i] % d[0] != 0:
		d[0] = 1
		break
print(d[0])

### FIXED CODE ###

import functools
import fractions
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = []
d = []
co = 0
for i in range(a[0]):
	c.append(abs(b[i]-a[1]))
	if b[i]-a[1] > 0 and co == 0:
		c.insert(i,0)
		co += 1
if co == 0:
	c.append(0)

for i in range(len(c)-1):
	d.append(abs(c[i+1]-c[i]))
print(functools.reduce(fractions.gcd, d))
a, b = map(int, input().split())

horizontal_length = b * 2

uncovered_part = a - horizontal_length

if uncovered_part > 0:
  return
else:
  uncovered_part = 0
  
print uncovered_part
  

### FIXED CODE ###

a, b = map(int, input().split())

horizontal_length = b * 2

uncovered_part = a - horizontal_length

if uncovered_part < 0:
  uncovered_part = 0
  
print(str(uncovered_part))
n, d = map(int, input().split())
count = 0
x_list = (list(map(int, input().split())) for _ in range(n))

for i in range(n-1):
    for j in range(i+1, n):
        count += (sum((a-b)**2 for a,b in zip(x_list[i], x_list[j]))**0.5).is_integer
print(count)

### FIXED CODE ###

n, a, b = map(int, input().split())
print(min(a*n, b))
N,K = map(int, input().split()))
h = list(map(int, input().split()))
r = 0
for j in range(N):
  if int(h[j]) >= K:
    r += 1
print(r)


### FIXED CODE ###

N,K = list(map(int, input().split()))
h = list(map(int, input().split()))
r = 0
for j in range(N):
  if int(h[j]) >= K:
    r += 1
print(r)
a = input()
print('A') if c.isupper() is True else print('B')

### FIXED CODE ###

a = input()
print('A') if a.isupper() is True else print('a')
l, r = map(int, input().split())
if r - l >= 2019:
    print(0)
    exit()
minn = 2*(10**9)*2
for i in range(l, r+1):
    for j in range(i+1, r+1):
        if minn > i * j % 2019:
        minn = min(minn, i * j % 2019)
print(minn)

### FIXED CODE ###

l, r = map(int, input().split())
if r - l >= 2019:
    print(0)
    exit()
minn = 2*(10**9)*2
for i in range(l, r+1):
    for j in range(i+1, r+1):
        minn = min(minn, i * j % 2019)
print(minn)
n = int(input())
a = int(input())
b = int(input())

c = 0
d = a + b -n
if (a > b):
    c = b
else:
    c = a

if (d < 0):
    d = 0
    
print(str(c) + " " + str(d))

### FIXED CODE ###

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

c = 0
d = a + b -n
if (a > b):
    c = b
else:
    c = a

if (d < 0):
    d = 0
    
print(str(c) + " " + str(d))
from functools import reduce 
from operator import add

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

pt_a = 0
pt_b = 0

arr = arr.sort(reverse=True)

for ind, num in enumerate(arr):
  if ind % 2 == 0:
    pt_a += num
  else:
    pt_b += num

print(pt_a - pt_b)

### FIXED CODE ###

from functools import reduce 
from operator import add
 
n = int(input())
arr = list(map(int, input().split()))
 
pt_a = 0
pt_b = 0
 
arr.sort(reverse=True)
 
for ind, num in enumerate(arr):
  if ind % 2 == 0:
    pt_a += num
  else:
    pt_b += num
 
print(pt_a - pt_b)
import sys
input = sys.stdin.readline

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]
con=[[] for _ in range (N+1)]
inf = float("inf")

allcost = [ -inf] * (N+1)
allcost[1] = 0

for i in range(M):
    a,b,c = abc[i]
    con[a].append(b)

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
def dfs(a):
  if N in con[a]:
    return True
  if len(con[a])==0:
    return False
  tmp=False 
  for ch in con[a]:
    if dfs(ch):
      tmp=True 
      break
  return tmp
for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        if dfs(a):
          print("inf")
          exit(0)

print(allcost[N])





### FIXED CODE ###

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

N,M = map(int, input().split())
abc = [[int(j) for j in input().split()] for _ in range(M)]
con=[[] for _ in range (N+1)]
inf = float("inf")

allcost = [ -inf] * (N+1)
allcost[1] = 0

for i in range(M):
    a,b,c = abc[i]
    con[a].append(b)

for n in range(1, N):
    for edge in range(M):
        a,b,c = abc[edge]
        if allcost[b] < allcost[a] + c:
            allcost[b] = allcost[a] + c
neg=[False]*(N+1)
for edge in range(M):
    a,b,c = abc[edge]
    if allcost[a] + c > allcost[b]:
        neg[b]=True
    if neg[a]==True:
      neg[b]=True
if neg[N]:
  print("inf")
  exit(0)
print(allcost[N])
a,b,c = input()
A = 0
if a == o:
  A += 1
if b == o:
  A += 1
if c == o:
  A += 1

if A == 3:
  print(1000)
if A == 2:
  print(900)
if A == 1:
  print(800)
if A == 0:
  print(700)

### FIXED CODE ###

a,b,c = input()
A = 0
if a == "o":
  A += 1
if b == "o":
  A += 1
if c == "o":
  A += 1
 
if A == 3:
  print(1000)
if A == 2:
  print(900)
if A == 1:
  print(800)
if A == 0:
  print(700)
n, k = input.split(' ')
n, k = int(n), int(k)
maxval = k - n
minval = k / n
print(maxval - minval)

### FIXED CODE ###

n, k = input().split(' ')
n, k = int(n), int(k)
maxval = 1
if k == 1:
    print(0)
else:
    while n - maxval - k + 1 != 0:
        maxval += 1
    print(maxval - 1)
from collections import deque
n = int(input())
l = deque()
count = set([])
for _ in range (n):
    cmd = input().split(' ')
    if cmd[0]=='insert':
        l.appendleft(int(cmd[1]))
        if not int(cmd[1]) in count:
            count.add(int(cmd[1]))
    if cmd[0]=='delete':
        if len(l) !=0 and int(cmd[1]) in count:
            l.remove(int(cmd[1]))
    if cmd[0]=='deleteFirst':
        l.popleft()
    if cmd[0]=='deleteLast':
        l.pop()
print(*l)


### FIXED CODE ###

from collections import deque
n = int(input())
l = deque()
for _ in range (n):
    cmd = input().split(' ')
    if cmd[0]=='insert':
        l.appendleft(cmd[1])  
    if cmd[0]=='delete':
        try:l.remove(cmd[1])
        except :pass
    if cmd[0]=='deleteFirst':
        l.popleft()
    if cmd[0]=='deleteLast':
        l.pop()
print(*l)
n, w = map(int, input().split())

weights = [0]*n
values = [0]*n

for i in range(n):
    weights[i], values[i] = map(int, input().split())

v = sum(values)

dp = [[float('inf') for _ in range(v+1)] for _ in range(n+1)]

for i in range(n+1):
    dp[i][0] = 0

for i in range(1, n+1):
    for j in range(1, v+1):
        if v[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(w[i] + dp[i-1][j-v[i]], dp[i-1][j])

for j in range(v+1):
    if dp[-1][j] == w:
        print(j)

### FIXED CODE ###

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

weights = [0]*n
values = [0]*n

for i in range(n):
    weights[i], values[i] = map(int, input().split())

v = sum(values)

dp = [[float('inf') for _ in range(v+1)] for _ in range(n+1)]

for i in range(n+1):
    dp[i][0] = 0

for i in range(1, n+1):
    for j in range(1, v+1):
        if values[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(weights[i-1] + dp[i-1][j-values[i-1]], dp[i-1][j])

for j in range(v,-1,-1):
    if dp[-1][j] <= w:
        print(j)
        break
import numpy as np

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
p = np.array([k for i in range(n)])
for i in a:
  p = p - 1 
  p[i-1] += 1
for i in p:
  if i > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]
lena = len(a)
p = [k-lena for i in range(n)]
for i in a:
  p[i-1] += 1
for i in p:
  if i > 0:
    print('Yes')
  else:
    print('No')
N, M = input().split()
print("Yes" if N == M else "No")

### FIXED CODE ###

N, M = input().split()
print("Yes" if N == M else "No")
N, K = [int(i) for i in input().split(' ')]

min_value = 0

count = 0
while True:
  if min_value < abs(N - K):
    count =+ 1
    if count > 1:
	    break
    else:
		N = abs(N - K)
		min_value = N		
  else:
	N = abs(N - K)
	min_value = N
    
print(min_value)	

### FIXED CODE ###

N, K = [int(i) for i in input().split(' ')]

def res():
  if N == K:
    return 0
  elif N > K:
    return N % K if K - (N % K) > (N % K) else K - (N % K)
  else :
    return abs(N - K) if abs(N - K) < abs(abs(N-K) - K) else abs(abs(N-K) - K)

print(res())
H,M = map(int,input().split())
if H == 1 or M ==1 :
    print(1)
else :
    prnt(int((H*M +1)//2))

### FIXED CODE ###

import math
H,M = map(int,input().split())
if H == 1 or M ==1 :
    print(1)
else :
    print(math.ceil((H*M)/2))
s=input()
a="AKIHABARA"
j=0
for i in s:
    if i==a[j]:
        j+=1
    elif j<8:
        if i==a[j+1] and a[j]=="A":
            j+=2
    else:
        print("NO")
        exit()
print("YES") 

### FIXED CODE ###

a=["KIH","B","R",""]
ans=[]
aaa=[]
for i in range(16):
    b=""
    for j,k in enumerate(a):
        if ((i >> j) & 1):
            b+="A"
        b+=k
    ans.append(b)
print("YES" if input() in ans else "NO")
a,b,c = map(int,input().split())

if a==b!=c:
  print("Yes")
elif c==b!=a:
  print("Yes")
elif a!=b=c:
  print("Yes"):
else:
  print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())

if a==b and b==c:
  print("No")
elif a==b or b==c or c==a :
  print("Yes")
  
else:
  print("No")
s_1,s_2,s_3 = input().split()
if s_1 == s_2 == s_3:
  print("No")
else:
  print("Yes")
  

### FIXED CODE ###

S = input()
if S == "AAA" or S == "BBB":
  print("No")
else:
  print("Yes")
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

A,B = MI()

if B > 1:
    q1,r1 = (B-1)//50,(B-1)%50
    q1 += 1
else:
    q1 = 0
if A > 1:
    q2,r2 = (A-1)//50,(A-1)%50
    q2 += 1
else:
    q2 = 0

print(2*(q1+q2),100)

for i in range(2*q1):
    if i % 2 == 1:
        print(''.join(['.']*100))
    elif i != 2*q1-2:
        print(''.join(*['.','#']*50))
    else:
        print(''.join(['.','#']*r1 + ['.']*(100-2*r1)))

for i in range(2*q2):
    if i % 2 == 0:
        print(''.join(['#']*100))
    elif i != 2*q2-1:
        print(''.join(['#','.']*50))
    else:
        print(''.join(['#','.']*r2 + ['#']*(100-2*r2)))


### FIXED CODE ###

import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())

A,B = MI()

q1,r1 = (B-1)//50,(B-1)%50
q1 += 1
q2,r2 = (A-1)//50,(A-1)%50
q2 += 1

if B > 1 and A > 1:
    print(2*(q1+q2),100)
elif (B == 1 and A > 1) or (B > 1 and A == 1):
    print(2*(q1+q2)-1,100)
else:
    print(2,100)

if B > 1:
    for i in range(2 * q1):
        if i % 2 == 1:
            print(''.join(['.'] * 100))
        elif i != 2 * q1 - 2:
            print(''.join(['.', '#'] * 50))
        else:
            print(''.join(['.', '#'] * r1 + ['.'] * (100 - 2 * r1)))
else:
    print(''.join(['.']*100))


if A > 1:
    for i in range(2 * q2):
        if i % 2 == 0:
            print(''.join(['#'] * 100))
        elif i != 2 * q2 - 1:
            print(''.join(['#', '.'] * 50))
        else:
            print(''.join(['#', '.'] * r2 + ['#'] * (100 - 2 * r2)))
else:
    print(''.join(['#']*100))
h, w = map(int, input().split())
a = [input().split() for i in range(h)]
for i in range(h):
  for j in range(w):
    a[i][w] == "snuke":
      print(chr(ord("A") + j) + str(i + 1))
      exit()

### FIXED CODE ###

w = []
for i in range(ord("A"), ord("Z") + 1):
  w.append(chr(i))
  
a, b = map(int, input().split())
for i in range(a):
  row = input().split()
  for j in range(b):
    if row[j] == "snuke":
      print(w[j] + str(i + 1))
n,m,k=map(int,input().split())
MOD=998244353

def prepare(n, MOD):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs

a,b=prepare(n-1,MOD)
ans,s=0,(m*pow(m-1,n-k-2,MOD))%MOD
for x in range(k,-1,-1):
    s*=(m-1)
    s%=MOD
    ans+=(s*a*b[x]*b[n-x-1])%MOD
    ans%=MOD
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
MOD=998244353

def prepare(n, MOD):
    # n! の計算
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return fn, invs

a,b=prepare(n-1,MOD)
ans,s=0,(m*pow(m-1,n-k-1,MOD))%MOD
for x in range(k,-1,-1):
    ans+=(s*a*b[x]*b[n-x-1])%MOD
    ans%=MOD
    s*=(m-1)
    s%=MOD
print(ans)
H , W = input().split()
W = int(W)
H = int(H)
ans = int(0)

#Wが偶数なら(W//2)*H
#W.Hが奇数なら((W+1)//2)*((H+1)//2) + ((W - 1)//2*(H - 1)//2)
#Wが奇数Hが偶数(W+1)//2*(H//2) + ((W - 1)//2)*(H//2)

if(W == 1 or H == 1):
    ans = 1
elif(W%2 == 0):
    ans = (W//2)*H
elif(W%2 == 1 and H%2==1):
    ans = (((W+1)//2)*((H+1)//2)) + (((W - 1)//2)*((H - 1)//2))
elif(W%2 == 1 and H%2 ==0):
    ans = (((W+1)//2)*(H//2)) + (((W - 1)//2)*(H//2))
print(ans)

### FIXED CODE ###

Term = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(Term[K-1])
n=int(input())
a=list(map(int,input().split()))
#print(n)
#print(a)
count=0
i=0
flag=True
while(flag):
    flag=False
    for i in range(n):
        if(flag==True):
            a[i]=a[i]*3
        elif(a[i]%2==0):
            #print(i)
            a[i]=a[i]/2
            count+=1
            flag=True
        else:
            a[i]=a[i]*3
print(count)

### FIXED CODE ###

a,b = map(int,input().split())
#if((a<0 or a>16) or (b<0 or b>16) or (a+b>16)):
    #print("error\n")
count=16
flag=False
pic=0 # 0=a,1=b
while(count>0):
    if(pic==0):
        a-=1
        count-=1
        pic=1    
    elif(pic==1):
        pic=0
        b-=1
        count-=1
    if(a<=0 and b<=0):
        flag=True
        break
if(flag==True):
    print("Yay!")
else:
    print(":(")
N,A,B = map(int, input().split())

line = 'b'*A + 'r'*B

for i in 10**100:
  line += line
  if len(line) >= N:
    break
   
ans = line.count('b')
print(ans)

### FIXED CODE ###

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

count = N//(A+B)
amari = N%(A+B)

if amari < A:
  c = amari
else:
  c = A
  
ans = A * count + c
print(ans)
import sys


def Sieve(N, AList):
    AList.sort()
    N_NotDivisible = 0
    while( len(AList) > 0 ):
        if(len(AList) > 1):
            if(AList[0]!= AList[1]):
                N_NotDivisible+= 1
                value = AList[0]
                pops = [0]
                for i in range(1, N):
                    if(AList[i]%value==0):
                        pops.append(i)
                AList.pop(pops)
            else:
                index = 2
                while(index < len(AList) and AList[index-1] == AList[index]):
                    index += 1
                for i in range(index):
                    AList.pop(0)

        else:
            N_NotDivisible+= 1
            break
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)


### FIXED CODE ###

import sys

def Sieve2(N, AList, Bools, Max_A):
    N_NotDivisible = 0
    value = 0
    for i in range(N):
        if(AList[i]>value):
            value = AList[i]
            if(Bools[value]==True):
                N_NotDivisible += 1

            for j in range(2, Max_A//value+1, 1 ):
                Bools[j*value] = False
    #print(Mins)
    return N_NotDivisible


if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()
    Max = 0
    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
        Max = max(AList[i], Max)
    Bools = [False] * (Max+1)
    AList.sort()
    Dups = []
    for Num in range(N):
        value = AList[Num]
        Bools[value] = True
        if(Num < N-1 and AList[Num] == AList[Num+1]):
            Dups.append(value)
    for Num in range(len(Dups)):
        value = Dups[Num]
        Bools[value] = False


    N_NotDivisible= Sieve2(N, AList, Bools, Max)
    print(N_NotDivisible)