





lowerCAmelCase_        =			{
    """0""": 1,
    """1""": 1,
    """2""": 2,
    """3""": 6,
    """4""": 24,
    """5""": 120,
    """6""": 720,
    """7""": 5040,
    """8""": 4_0320,
    """9""": 36_2880,
}

lowerCAmelCase_        =			{145: 145}

lowerCAmelCase_        =			{
    145: 0,
    169: 3,
    3_6301: 3,
    1454: 3,
    871: 2,
    4_5361: 2,
    872: 2,
}


def 			lowerCamelCase_		(					lowerCAmelCase:		int )->						int:
  if n in CACHE_SUM_DIGIT_FACTORIALS:
    return CACHE_SUM_DIGIT_FACTORIALS[n]
  _snake_case      : str														=		sum(DIGIT_FACTORIALS[let] for let in str(lowerCAmelCase ) )
  _snake_case      : Any														=		ret
  return ret


def 			lowerCamelCase_		(					lowerCAmelCase:		int			,							lowerCAmelCase:		set | None = None )->						int:
  _snake_case      : Union[str, Any]														=		previous or set()
  if n in CHAIN_LENGTH_CACHE:
    return CHAIN_LENGTH_CACHE[n]
  _snake_case      : Union[str, Any]														=		sum_digit_factorials(lowerCAmelCase )
  if next_number in previous:
    _snake_case      : int														=		0
    return 0
  else:
    previous.add(lowerCAmelCase )
    _snake_case      : Optional[Any]														=		1 + chain_length(lowerCAmelCase			,							lowerCAmelCase )
    _snake_case      : Optional[Any]														=		ret
    return ret


def 			lowerCamelCase_		(					lowerCAmelCase:		int = 60			,							lowerCAmelCase:		int = 1_00_00_00 )->						int:
  return sum(1 for i in range(1			,							lowerCAmelCase ) if chain_length(lowerCAmelCase ) == num_terms )


if __name__ == "__main__":
      print(F"""{solution() = }""")











def 			lowerCamelCase_		(					lowerCAmelCase:		str			,							lowerCAmelCase:		str )->						int:
  # The longer word should come first
  if len(lowerCAmelCase ) < len(lowerCAmelCase ):
    return levenshtein_distance(lowerCAmelCase			,							lowerCAmelCase )

  if len(lowerCAmelCase ) == 0:
    return len(lowerCAmelCase )

  _snake_case      : Dict														=		list(range(len(lowerCAmelCase ) + 1 ) )

  for i, ca in enumerate(lowerCAmelCase ):
    _snake_case      : Optional[int]														=		[i + 1]

    for j, ca in enumerate(lowerCAmelCase ):
      # Calculate insertions, deletions and substitutions
      _snake_case      : Optional[Any]														=		previous_row[j + 1] + 1
      _snake_case      : Optional[int]														=		current_row[j] + 1
      _snake_case      : Union[str, Any]														=		previous_row[j] + (ca != ca)

      # Get the minimum to append to the current row
      current_row.append(min(lowerCAmelCase			,							lowerCAmelCase			,							lowerCAmelCase ) )

    # Store the previous row
    _snake_case      : str														=		current_row

  # Returns the last element (distance)
  return previous_row[-1]


if __name__ == "__main__":
      lowerCAmelCase_        =			input("""Enter the first word:\n""").strip()
      lowerCAmelCase_        =			input("""Enter the second word:\n""").strip()

      lowerCAmelCase_        =			levenshtein_distance(first_word, second_word)
      print(F"""Levenshtein distance between {first_word} and {second_word} is {result}""")




