# from collections import defaultdict
# M = 10**3

# dp = [0 for _ in range(M + 1)]
# for i in range(1, M):
#     dp[i] = 1 + dp[i - sum(int(c) for c in str(i))]
    
# def jump_to_zero(xs):
#     return list(map(lambda x: dp[x], xs))

    
# def f(n):
#     cnt = 0
#     while n > 0:
#         n -= sum(int(c) for c in str(n))
#         cnt += 1
#     return cnt
ROOT_LEN = 4
CELL_LEN = 2
def digitSum(n:int) -> int:
    return sum(int(c) for c in str(n))
    # sum = 0
    # while n > 0: sum += n % 10; n = n // 10
    # return sum
powersOfTen = []
def pow10(n:int) -> int:
    return 10**n

rootVal = 0
rootMemo = dict()
def rootSteps(prevDSum:int) -> int:
    global rootVal
    global rootMemo
    if (prevDSum, rootVal) in rootMemo:
        stepCount = rootMemo[(prevDSum, rootVal)][0]
        rootVal = rootMemo[(prevDSum, rootVal)][1]
        return stepCount
    prevRootVal = rootVal 
    stepCount = 0
    print("before ", prevDSum, prevRootVal)
    while rootVal >= 0:
        # print("rootVal :", rootVal)
        rootVal -= (digitSum(rootVal) + prevDSum)
        stepCount += 1
        if rootVal == 0 and prevDSum == 0:
            return stepCount
    print("step :", stepCount)
    print("rootVal before:", rootVal, "dSum :", prevDSum)
    rootVal += pow10(ROOT_LEN)
    print("rootVal after:", rootVal)
    rootMemo[(prevDSum, prevRootVal)] = (stepCount, rootVal)
    print("root Memo", rootMemo)
    return stepCount
defaultCellSize = pow10(CELL_LEN)
cellMemos = []
def cellSteps(index:int, prevDSum:int, cellSize=defaultCellSize) -> int:
    global rootVal
    if index == 0:
        return rootSteps(prevDSum)
    stepCount = 0
    if prevDSum > 0 and (prevDSum, rootVal) in cellMemos[index-1]:
        stepCount = cellMemos[index-1][(prevDSum, rootVal)][0]
        rootVal = cellMemos[index-1][(prevDSum, rootVal)][1]
        return stepCount
    prevRootVal = rootVal
    for d in range(cellSize-1, -1, -1):
        stepCount += cellSteps(index-1, prevDSum + digitSum(d))
    cellMemos[index-1][(prevDSum, prevRootVal)] = (stepCount, rootVal)
    
    return stepCount
def a(n):
    global rootVal
    print(ROOT_LEN)
    if n <= ROOT_LEN:
        rootVal = pow10(n)
        return rootSteps(0)
    print("ok")
    rootVal = pow10(ROOT_LEN)-1
    n -= ROOT_LEN
    cellCount = n // CELL_LEN
    topCell = n % CELL_LEN
    while len(cellMemos) <= cellCount:
        cellMemos.append(dict())
    
    return 1+cellSteps(cellCount+1, 0, pow10(topCell))
# for i in range(1,4):
#     print(a(i))
r = a(5)
print(r)
# dct = defaultdict(list)
# for n in range(9000, 10000):
#     r = f(n)
#     dct[r].append(n)
# for k, v in dct.items():
#     print(k, v)
"""
2724 [50090, 50091, 50092, 50093, 50094, 50095, 50096, 50097, 50098, 50099]
2725 [50100, 50101, 50102, 50103, 50104, 50105, 50106, 50107, 50108, 50109]
2726 [50110, 50111, 50112, 50113, 50114, 50115, 50116, 50117, 50118, 50119]
2727 [50120, 50121, 50122, 50123, 50124, 50125, 50126, 50127, 50128, 50129]
2728 [50130, 50131, 50132, 50133, 50134, 50135, 50136, 50137, 50138, 50139]
2729 [50140, 50141, 50142, 50143, 50144, 50145, 50146, 50147, 50148, 50149, 50150, 50151, 50152, 50153, 50154, 50155, 50156, 50157, 50158, 50159]
2730 [50160, 50161, 50162, 50163, 50164, 50165, 50166, 50167, 50168, 50169, 50170, 50171, 50172, 50173, 50174, 50175, 50176, 50177, 50178, 50179]
2731 [50180, 50181, 50182, 50183, 50184, 50185, 50186, 50187, 50188, 50189, 50190, 50191, 50192, 50193, 50194, 50195, 50196, 50197, 50198, 50199]
2732 [50200, 50201, 50202, 50203, 50204, 50205, 50206, 50207, 50208, 50209]
2733 [50210, 50211, 50212, 50213, 50214, 50215, 50216, 50217, 50218, 50219]
2734 [50220, 50221, 50222, 50223, 50224, 50225, 50226, 50227, 50228, 50229]
2735 [50230, 50231, 50232, 50233, 50234, 50235, 50236, 50237, 50238, 50239, 50240, 50241, 50242, 50243, 50244, 50245, 50246, 50247, 50248, 50249]
2736 [50250, 50251, 50252, 50253, 50254, 50255, 50256, 50257, 50258, 50259, 50260, 50261, 50262, 50263, 50264, 50265, 50266, 50267, 50268, 50269]
2737 [50270, 50271, 50272, 50273, 50274, 50275, 50276, 50277, 50278, 50279, 50280, 50281, 50282, 50283, 50284, 50285, 50286, 50287, 50288, 50289]
2738 [50290, 50291, 50292, 50293, 50294, 50295, 50296, 50297, 50298, 50299]
"""