Harryxun/stf_run huggingface dataset:
import sys
N, L = map(int, input().split())
W = []
V = []
for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

sys.setrecursionlimit(10**8)

dp = [[-1] * 10010 for _ in range(110)]


def knap(i, j):
    if dp[i][j] >= 0:
        return dp[i][j]

    if i == N:
        dp[i][j] = 0
    elif j < W[i]:
        dp[i][j] = knap(i+1, j)
    else:
        dp[i][j] = max(knap(i+1, j), knap(i+1, j - W[i]) + V[i])

    return dp[i][j]


print(knap(0, L))


### FIXED CODE ###

N, W = map(int, input().split())
T = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] + [-1] * W for _ in range(N+1)]
dp[0] = [0] * (W+1)

for i in range(1, N+1):
    for w in range(1, W+1):
        dp[i][w] = max(dp[i-1][w], dp[i-1][w - T[i-1][0]] + T[i-1]
                       [1]) if w - T[i-1][0] >= 0 else dp[i-1][w]

# print(*dp, sep='\n')
print(dp[N][W])
s = input()
if s in '9':
  print('Yes')
 else:
  print('No')

### FIXED CODE ###

s = input()
if '9' in s:
  print('Yes')
else:
  print('No')
def segfunc(x, y): return max(x, y)

def update(i, x):
    i += noden-1
    node[i] = x
    while i:
        i = (i-1)//2
        node[i] = segfunc(node[i*2+1], node[i*2+2])

def query(l, r):
    L = l + noden
    R = r + noden
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, node[R - 1])
        if L & 1:
            s = segfunc(s, node[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

N, K = map(int, input().split())
MAX_N = 2**(N-1).bit_length()
a = [int(input()) for _ in range(N)]
node = [0] * (2 * MAX_N - 1)
noden = MAX_N
INF = 0
ma = max(a)
ans = 0
for i in a:
    tmp = query(max(i - K, 0), min(ma, i + K) + 1)
    update(i, tmp + 1)
    ans = max(ans, tmp + 1)
print(ans)


### FIXED CODE ###

def segfunc(x, y): return max(x, y)

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    ba = 0  # Num. of str that the first letter is B and the last one is A.
    xb = 0  # Num. of str that the last letter is B and the first one is not A.
    ax = 0  # Num. of str that the first letter is A and the last one is not B.
    for _ in range(N):
        s = str(input().strip())

        # Count the number of AB contained in the initial strings.
        for i in range(len(s)):
            if s[i:i+2] == 'AB':
                ans += 1

        if s[0] == 'B' and s[-1] == 'A':
            ba += 1
        elif s[0] == 'B':
            xb += 1
        elif s[-1] == 'A':
            ax += 1

    if max(xb, ax) == 0:
        # N of ba make N-1 new "AB".
        # BxxA + BxxA + ... + BxxA -> BxxABxxAB...ABxxA
        ans += ba - 1

    else:  # There is at least one bx or ax.
        # N of ba make N-1 new "AB" and a ba.
        #   ba + ba + ... + ba -> baba...ba = ba
        # The last remaining ba and bx/ax make a new "AB" and a new bx/ax.
        #   ba + bx -> bABx = bx,  xa + ba -> xABa = xa
        # Then, bx and xa make a new "AB".
        #   xa + bx -> xABx 
        ans += ba + min(xa, bx)

    return ans


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


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    ans = 0
    ba = 0  # Num. of str that the first letter is B and the last one is A.
    xa = 0  # Num. of str that the last letter is A and the first one is not B.
    bx = 0  # Num. of str that the first letter is B and the last one is not A.
    for _ in range(N):
        s = str(input().strip())

        # Count the number of AB contained in the initial strings.
        for i in range(len(s)):
            if s[i:i+2] == 'AB':
                ans += 1

        if s[0] == 'B' and s[-1] == 'A':
            ba += 1
        elif s[-1] == 'A':
            xa += 1
        elif s[0] == 'B':
            bx += 1

    if ba == 0:
        # One xa ans one bx make one new "AB".
        #   xa + bx -> xABx
        ans += min(xa, bx)

    elif max(xa, bx) == 0:
        # N of ba make N-1 new "AB".
        # BxxA + BxxA + ... + BxxA -> BxxABxxAB...ABxxA
        ans += ba - 1

    else:  # There is at least one bx or ax and at least one ba.
        # N of ba make N-1 new "AB" and a ba.
        #   ba + ba + ... + ba -> baba...ba = ba
        # The last remaining ba and bx/ax make a new "AB" and a new bx/ax.
        #   ba + bx -> bABx = bx,  xa + ba -> xABa = xa
        # Then, bx and xa make a new "AB".
        #   xa + bx -> xABx 
        ans += ba + min(xa, bx)

    return ans


if __name__ == '__main__':
    print(main())
n,k=map(int,input().split())
hps=list(map(int,input().split()))
hps.sort()
if k>n:
  print(n)
elif k==n:
  print(k)
else:
  ans=k
  for i in range(k):
    hps.pop()
  ans+==sum(hps)
  print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
hps=list(map(int,input().split()))
hps.sort()
if k>n:
  print(0)
elif k==n:
  print(0)
else:
  ans=0
  for i in range(k):
    hps.pop()
  ans+=sum(hps)
  print(ans)
n, m = map(int, input().split())
xyz = sorted([map(int, input().split()) for _ in range(m)])

ans, find = 0, set([])
for x, y, z in xyz:
    if not (x or y) in find:
        ans += 1
    find.add(x)
    find.add(y)
print(ans + (n - len(find)))


### FIXED CODE ###

class Unionfind():  # 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 roots(self):  # 根のリスト
        return [i for i, x in enumerate(self.parents) if x < 0]


n, m = map(int, input().split())
xyz = sorted([list(map(int, input().split())) for _ in range(m)])

uf = Unionfind(n)
for x, y, z in xyz:
    uf.union(x - 1, y - 1)
print(len(uf.roots()))
import sys
input = sys.stdin.readline

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def sieve_optimized(limit):
    # Preprocessing step takes O(N log log N) time complexity.
    n = limit
    # Filimitd all primes upto n  (including n)
    sievebound = (n-1)//2
    sieve = [-1]*(sievebound + 1)
    # sieve[0] = True
    crosslimit = (int(sievebound**0.5) - 1)
    for i in range(1, crosslimit + 1):
        if sieve[i] == -1:
            for j in range(2*i*(i+1), sievebound + 1, 2*i+1):
                sieve[j] = 2*i + 1
    return sieve

def factorization(n, sieve):
    # Factorisaton query takes O(log N) time after preprocessing.
    divs = [1]
    while n!=1:
        if n&1:
            div = sieve[(n-1)//2]
            if div == -1:
                divs.append(n)
                break
            else:
                n //= div
                divs.append(div)
        else:
            n >>= 1
            divs.append(2)

    return divs

maxnum = 10**6
sieve = sieve_optimized(maxnum)
n = int(input())
nums = list(map(int, input().split()))

seen = dict()
for i in nums:
    factors = factorization(i, sieve)
    for f in set(factors[1:]):
        if f in seen:
            seen[f] += 1
        else:
            seen[f] = 1

maxval = max(seen.values())

if maxval == n:
    print('not coprime')

elif 1 < maxval < n:
    print('setwise coprime')

else:
    print('pairwise coprime')

### FIXED CODE ###

import sys
input = sys.stdin.readline

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def sieve_optimized(limit):
    # Preprocessing step takes O(N log log N) time complexity.
    n = limit
    # Filimitd all primes upto n  (including n)
    sievebound = (n-1)//2
    sieve = [-1]*(sievebound + 1)
    # sieve[0] = True
    crosslimit = (int(sievebound**0.5) - 1)
    for i in range(1, crosslimit + 1):
        if sieve[i] == -1:
            for j in range(2*i*(i+1), sievebound + 1, 2*i+1):
                sieve[j] = 2*i + 1
    return sieve

def factorization(n, sieve):
    # Factorisaton query takes O(log N) time after preprocessing.
    divs = [1]
    while n!=1:
        if n&1:
            div = sieve[(n-1)//2]
            if div == -1:
                divs.append(n)
                break
            else:
                n //= div
                divs.append(div)
        else:
            n >>= 1
            divs.append(2)

    return divs

maxnum = 10**6 + 1
sieve = sieve_optimized(maxnum)

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

seen = dict()
maxval = 0
for i in nums:
    factors = factorization(i, sieve)
    if len(factors) <= 1: continue
    for f in set(factors[1:]):
        if f in seen:
            seen[f] += 1
            maxval = max(maxval, seen[f])
        else:
            seen[f] = 1


if maxval == n:
    print('not coprime')

elif 1 < maxval < n:
    print('setwise coprime')

else:
    print('pairwise coprime')
from sys import stdin

n = stdin.readline().rstrip().split()
a = stdin.readline().rstrip().split()

total = 1
for i in a:
    total = total*int(i)
	if(total > 1000000000000000000):
      total = -1
      break
    
print(total)

### FIXED CODE ###

from sys import stdin
import sys

n = stdin.readline().rstrip().split()
a = stdin.readline().rstrip().split()

if '0' in a:
    print(0)
    sys.exit()

total = 1
for i in a:
    total = total*int(i)

    if(total > 1000000000000000000):
        print(-1)
        sys.exit()

print(total)
from collections import defaultdict
import sys
input = sys.stdin.readline


class Osak:
    def __init__(self, max_number=10 ** 6):
        self.max_number = max_number
        self.table = list(range(max_number + 1))
        self.calc_minimum_prime()

    def calc_minimum_prime(self):
        self.table[1] = 0
        for base in range(2, self.max_number + 1):
            if self.table[base] != base:
                continue
            for num in range(base, self.max_number+1, base):
                self.table[num] = base

    def judge_is_prime(self, num):
        return self.table[num] == num

    def get_factors(self, num):
        factors = set()
        while num > 1:
            prime = self.table[num]
            factors.add(prime)
            num //= prime
        return factors

    def factorize(self, num):
        factors = defaultdict(int)
        while num > 1:
            prime = self.table[num]
            factors[prime] += 1
            num //= prime
        return factors


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

    osak = Osak(max(A))
    prime_count = defaultdict(int)
    for a in A:
        factors = osak.get_factors(a)
        for factor in factors:
            prime_count[factor] += 1

    ans = max(prime_count.values())

    if ans == 1:
        print("pairwise coprime")
    elif ans < n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


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

    counts = [0] * (10**6 + 1)
    for a in A:
        counts[a] += 1

    ans = 1
    for i in range(2, 10**6+1):
        co_primes = 0
        for j in range(i, 10**6+1, i):
            co_primes += counts[j]
        if ans < co_primes:
            ans = co_primes

    if ans == 1:
        print("pairwise coprime")
    elif ans < n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()
x,y = map(int,input().split())
if y>=2*x and y<=4*x and y%2==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a = list(map(int,input().split()))
for i in range(5):
  if a[i]==0:
    print(i+1)
    break
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N, K = [int(x) for x in input().split()]
height = []
for _ in range(N):
    height.append(int(input()))

height.sort()
height.reverse()
sublist = []
for i in range(N-K+1):
    hmaxhmin = height[i]-heght[i+K]
    sublist.append(hmaxhmin)

print(min(sublist))



### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N, K = [int(x) for x in input().split()]
height = []
for _ in range(N):
    height.append(int(input()))

height.sort()
height.reverse()
sublist = []
for i in range(N-K+1):
    hmaxhmin = height[i]-height[i+K-1]
    sublist.append(hmaxhmin)

print(min(sublist))
n = int(input())
s = ["" for i in range(n)]
for j in range(n):
    s[j] = str(input())
s.sort()
count = [0 for _ in range(len(set(s)))]
l = 0
name = list(sorted(set(s)))
for k in range(n-1):
    count[l] += 1
    if(s[k] != s[k+1]):
        l += 1
if(s[-1] == s[-2]):
    count[-1] += 1
else:
    count.append(1)

m_v = max(count)
ansnum = []

for h in range(len(count)):
    if(count[h] == m_v):
        ansnum.append(name[h])

print(sorted(ansnum))

### FIXED CODE ###

n = int(input())
s = ["" for i in range(n)]
for j in range(n):
    s[j] = str(input())
s.sort()
count = [0 for _ in range(len(set(s)))]
l = 0
name = list(sorted(set(s)))
for k in range(n-1):
    count[l] += 1
    if(s[k] != s[k+1]):
        l += 1

count[-1] += 1

m_v = max(count)
ansnum = []

for h in range(len(count)):
    if(count[h] == m_v):
        ansnum.append(name[h])

print("\n".join(sorted(ansnum)))
n = input()
A = map(int, input().split())
import numpy as np
A = np.array(A)
B = []
for i in range(N):
    b = np.where(A==i+1)
    print(b[0][0]+1)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = [0]*n
for i in range(n):
  B[A[i]-1] = i + 1 
for i in range(n):
  print(B[i])
n = int(input())
A = list(map(int,input().split()))

dic = [False]*7

cnt = 0

for i in range(n):
  tmp = A[i] // 400
  if(tmp >= 8):
    cnt += 1
  else:
    dic[tmp] = True
  
print(str(sum(dic)) + ' ' + str(sum(dic) + cnt))

### FIXED CODE ###

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

dic = [False]*8

cnt = 0

for i in range(n):
  tmp = A[i] // 400
  if(tmp >= 8):
    cnt += 1
  else:
    dic[tmp] = True
if(sum(dic) == 0 and cnt > 0):
  print('1 ' + str(cnt))
else:
  print(str(sum(dic)) + ' ' + str(sum(dic) + cnt))
x = int(raw_input())
if (x >= 30):
 	print("Yes")
else:
	print("No")

### FIXED CODE ###

x = int(input())
if (x >= 30):
 	print("Yes")
else:
	print("No")
A, B = map(int, input().split())

a = int(A // 0.08) + 1
b = int(B // 0.1) + 1

ab = []
ab.append(min(a, b))
ab.append(max(a, b))

for i in ab:
    if int(i * 0.08) == A and int(i * 0.1) == B:
        print(f'{i}')
        exit(0)
        
print('-1')

### FIXED CODE ###

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

a = int(A // 0.08) + 1
b = int(B // 0.1) + 1

ab = []
ab.append(min(a, b))
ab.append(max(a, b))

for i in ab:
    if int(i * 0.08) == A and int(i * 0.1) == B:
        print(i)
        exit(0)

print('-1')
zn = int(input())
a = 0
b = 0
c = 0
d = 0
 
for i in range(n):
  S = str(input())
  if S == 'AC':
    a += 1
  elif S == 'WA':
    b += 1
  elif S == 'TLE':
    c += 1
  elif S == 'RE':
    d += 1
print('AC x '+str(a))
print('WA x '+str(b))
print('TLE x '+str(c))
print('RE x '+str(d))

### FIXED CODE ###

from collections import defaultdict
N = int(input())
d = defaultdict(int)

for _ in range(N):
  s = input()
  if s == 'AC':
    d[s] += 1
  elif s == 'WA':
    d[s] += 1
  elif s == 'TLE':
    d[s] += 1
  else:
    d[s] += 1
    
    
for k in ['AC', 'WA', 'TLE', 'RE']:
  print('{} x {}'.format(k, d[k]))
n,hp=map(int,input().split(" "))
la=[0 for i in range(n)]
lb=[0 for i in range(n)]
for i in range(n):
    la[i],lb[i]=map(int,input().split(" "))
cnt=0
ma=max(la)
lma=[i for i ,x in enumerate(la)  if x==ma]
mib=10**9
for i in lma:
    if lb[i]<mib:
        mib=lb[i]
        k=i
for i in range(n):
    if lb[i]>ma and i!=k:
        hp-=lb[i]
        cnt+=1
        if hp<0:
            print(cnt)
            exit(0)
        if hp<lb[k]:
            print(cnt+1)
            exit(0)
if lb[k]>ma:
    hp-=lb[k]
    cnt+=1
if hp%ma==0:
    print(cnt+int(hp/ma))
else:
    print(cnt+int(hp/ma)+1)

### FIXED CODE ###

N,H=map(int,input().split())
ab=[]
a=[]
b=[]

for i in range(N):
    ab.append(list(map(int,input().split())))
    a.append(ab[i][0])
    b.append(ab[i][1])

a.sort(reverse=True)
b.sort(reverse=True)
k=0
cnt=0

while a[0]<b[k]:
    H-=b[k]
    cnt+=1
    if H<=0:
        break
    k+=1
    if k==len(b):
        break

#print(cnt,H)
H=max(H,0)

if H%a[0]==0:
    cnt+=H//a[0]
else:
    cnt+=H//a[0]+1

print(cnt)
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
ans =[[0]*w for i in range(h)]
for i in range(m):
  a, b = map(int, input().split())
  a-=1
  b-=1
  hl[a]+=1
  wl[b]+=1
  ans[a][b]+=1

mh = 0
mhi = []
for i in range(h):
  if hl[i]>mh:
    mh = hl[i]
    mhi=[i]
  if hl[i]==mh:
    mhi.append(i)

wh = 0
whi = []
for i in range(w):
  if wl[i]>wh:
    wh = wl[i]
    whi=[i]
  if wl[i]==wh:
    whi.append(i)

for i in mhi:
  for j in whi:
    if ans[i][j]==0:
      print(mh+wh)
      quit()
print(mh+wh-1)
    

### FIXED CODE ###

from collections import deque
h, w, m = map(int, input().split())
hl=[0]*h
wl=[0]*w
mh=0
mw=0
mhi=deque([])
dic = {}
mwi=deque([])
#ans =[[0]*w for i in range(h)]
s = [list(map(int, input().split())) for i in range(m)]
 
for i in range(m):
  a, b = s[i]
  a-=1
  b-=1
  if not a in dic:
    dic[a] = {}
    dic[a][b]=1
  else:
    dic[a][b]=1
 
  hl[a]+=1
  if hl[a]>mh:
    mh=hl[a]
    mhi = [a]
  elif hl[a]==mh:
    mhi.append(a)
  
  wl[b]+=1
  if wl[b]>mw:
    mw=wl[b]
    mwi=[b]
  elif wl[b]==mw:
    mwi.append(b)
 
  #ans[a][b]+=1

for i in mhi:
  for j in mwi:
    if not j in dic[i]:
      print(mw+mh)
      quit()

print(mh+mw-1)
import sys
input = lambda: sys.stdin.readline().rstrip()
inp = sys.stdin.buffer.readline                               
def I(): return list(map(int,inp().split()))
from collections import Counter
from numpy import prod

n,=I()
s=input() 
cut=0
for i in range(len(s)):
    for j in range(i+1,len(s)):
        if 2*j-i>=len(s): break
        if len({s[i],s[j],s[2*j-i]})==3:
            cut+=1
d=Counter(s)
print(prod(list(d.values()))-cut)


            
                
        

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
inp = sys.stdin.buffer.readline                               
def I(): return list(map(int,inp().split()))
from collections import Counter
from numpy import prod

n=I()[0]
s=input() 
cut=0
for i in range(len(s)):
    for j in range(i+1,len(s)):
        if 2*j-i>=len(s): break
        if len({s[i],s[j],s[2*j-i]})==3:
            cut+=1
d=Counter(s)
if len(d)<3: print(0)
else: print(prod(list(d.values()))-cut)
import math
param = list(map(int, input()))
a = param[0]
b = param[1]
h = param[2]
m = param[3]
hrad = ( h / 12 ) * 360 + ( m / 60) * 30
mrad = ( m / 60 ) * 360
rad = hrad - mrad
print(rad)
if rad < 0:
    rad = -rad
else:
    if rad > 180:
        rad = 360 - rad
    else:
        pass
print(rad)
c = float((a**2 + b**2 - 2 * a * b * math.cos(math.radians(rad))) ** (0.5))
print(c)

### FIXED CODE ###

import math
a, b, h, m = map(int, input().split())
hrad = h * 30 + m * 0.5
mrad = m * 6
rad = hrad - mrad
if rad < 0:
    rad = -rad
else:
    if rad > 180:
        rad = 360 - rad
    else:
        pass
c = float((a**2 + b**2 - 2 * a * b * math.cos(math.radians(rad))) ** (0.5))
print(c)
N, M, X=map(int, input().split())
list=[0]*(N+1)
for i in range(M):
    list[map(int, input().split())]=1
min(sum(list.loc[0:X]), sum(list.loc(X+1:N+1)))

### FIXED CODE ###

N, M, X=map(int, input().split())
sum=sum(int(i)<X for i in input().split())
print(min(sum, M-sum))
import collections

n = int(input())
vs = [int(i) for i in input().split()]
evens = []
odds = []
for i,num in enumerate(vs):
    if i % 2 == 0:
        evens.append(num)
    elif i % 2 == 1:
        odds.append(num)

def plana():
    if (len(set(vs)) == 2) and (len(set(evens)) == 1) and (len(set(odds)) == 1):
        return 0
    elif (len(set(vs)) == 1):
        return len(evens)
    ec = collections.Counter(evens)
    oc = collections.Counter(odds)

    count = 0
    count += (len(evens) - ec.most_common()[0][1])
    count += (len(odds) - oc.most_common()[0][1])
    return count

# if len(set(vs)) == 1:
#     print(int(len(vs)/2))
# elif (len(set(evens)) == 1) and (len(set(odds)) == 1):
#     print(0)
# else:
print(len(odds))



### FIXED CODE ###

inums = input()
# [int(i)for i in input().split()]
nums = []
for i in inums:
    nums.append(int(i))
o = []
for n in nums:
    if n == 1:
        o.append("9")
    elif n==9:
        o.append("1")
    else:
        o.append(str(n))
print("".join(o))
def fill0(A,s,x,y):
	A[y][x] = 0
	if x < W-1 and A[y][x+1] == s: fill0(A,s,x+1,y)
	if y < H-1 and A[y+1][x] == s: fill0(A,s,x,y+1)
	if x > 0   and A[y][x-1] == s: fill0(A,s,x-1,y)
	if y > 0   and A[y-1][x] == s: fill0(A,s,x,y-1)

while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	ans = 0
	for y in range(H):
		for x in range(W):
			if A[y][x] in ["#","@","*"]:
				fill0(A,A[y][x],x,y)
				ans += 1
	print ans

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)
def solve(h,w,count,c):
    if 0 <= h < H and 0 <= w < W and A[h][w] == c:
        A[h][w] = count
        for dh,dw in zip([1,0,-1,0],[0,1,0,-1]):
            solve(h+dh,w+dw,count,c)
while 1:
    H,W = map(int,raw_input().split())
    if H == W == 0: break
    A = [list(raw_input()) for _ in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if type(A[h][w]) is not int:
                solve(h,w,count,A[h][w])
                count += 1
    print count
n=(int)input()
print(n**3)


### FIXED CODE ###

n=int(input())
print(n**3)
s=input()
num=len(s)-2
print(s[0]+num+s[num+1])

### FIXED CODE ###

s=input()
num=len(s)-2
print(s[0], num, s[num+1], sep="")
D,T,S=int(input().split())
if D/S<=T:
  print('Yes')
else:
  Print('No')

### FIXED CODE ###

D,T,S=map(int,input().split())
if D/S<=T:
  print('Yes')
else:
  print('No')
import functiontool
N = int(input())
K = int(input())

@functools.lru_cache(user_function)
def func(num,counter):
    remain = num%10
    quotient = num//10
    
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))

### FIXED CODE ###

N = int(input())
K = int(input())


def func(num,counter):
    remain = num%10
    quotient = num//10
    
    
    if counter == 0:
        return 1
    
    if num<10:
        if counter ==1:
            return num
        else:
            return 0

    return func(quotient,counter-1)*remain + func(quotient-1,counter-1)*(9-remain) + func(quotient,counter)

print(func(N,K))