

'''simple docstring'''






class 			lowerCAmelCase__     :




     """simple docstring"""





     def __init__(		self						:	Optional[int]	)       ->			List[str]:
          '''simple docstring'''




          a__   :      Any     =						''''''
          a__   :      List[str]     =						''''''
          a__   :      Optional[Any]     =						[]







     def 			__lowerCAmelCase	(		self						:	str      ,						A__						:	str      ,						A__						:	str	)       ->			int:
          '''simple docstring'''




          if m == -1:
               return n + 1
          elif n == -1:
               return m + 1
          elif self.dp[m][n] > -1:
               return self.dp[m][n]
          else:
               if self.worda[m] == self.worda[n]:
                    a__   :      Tuple     =						self.__min_dist_top_down_dp(m - 1      ,						n - 1	)
               else:
                    a__   :      Optional[Any]     =						self.__min_dist_top_down_dp(lowerCAmelCase__      ,						n - 1	)
                    a__   :      Dict     =						self.__min_dist_top_down_dp(m - 1      ,						lowerCAmelCase__	)
                    a__   :      Dict     =						self.__min_dist_top_down_dp(m - 1      ,						n - 1	)
                    a__   :      List[str]     =						1 + min(lowerCAmelCase__      ,						lowerCAmelCase__      ,						lowerCAmelCase__	)

               return self.dp[m][n]







     def 			__lowerCAmelCase	(		self						:	Tuple      ,						A__						:	int      ,						A__						:	Optional[int]	)       ->			int:
          '''simple docstring'''




          a__   :      int     =						worda
          a__   :      str     =						worda
          a__   :      Dict     =						[[-1 for _ in range(len(lowerCAmelCase__	)	)] for _ in range(len(lowerCAmelCase__	)	)]

          return self.__min_dist_top_down_dp(len(lowerCAmelCase__	) - 1      ,						len(lowerCAmelCase__	) - 1	)







     def 			__lowerCAmelCase	(		self						:	Optional[Any]      ,						A__						:	List[str]      ,						A__						:	Any	)       ->			int:
          '''simple docstring'''




          a__   :      Any     =						worda
          a__   :      Optional[Any]     =						worda
          a__   :      Tuple     =						len(lowerCAmelCase__	)
          a__   :      Optional[int]     =						len(lowerCAmelCase__	)
          a__   :      Dict     =						[[0 for _ in range(n + 1	)] for _ in range(m + 1	)]

          for i in range(m + 1	):
               for j in range(n + 1	):
                    if i == 0:  # first string is empty
                         a__   :      Any     =						j
                    elif j == 0:  # second string is empty
                         a__   :      Optional[Any]     =						i
                    elif worda[i - 1] == worda[j - 1]:  # last characters are equal
                         a__   :      int     =						self.dp[i - 1][j - 1]
                    else:
                         a__   :      str     =						self.dp[i][j - 1]
                         a__   :      Tuple     =						self.dp[i - 1][j]
                         a__   :      Optional[Any]     =						self.dp[i - 1][j - 1]
                         a__   :      Optional[Any]     =						1 + min(lowerCAmelCase__      ,						lowerCAmelCase__      ,						lowerCAmelCase__	)
          return self.dp[m][n]


if __name__ == "__main__":
 __SCREAMING_SNAKE_CASE     =						EditDistance()

 print('****************** Testing Edit Distance DP Algorithm ******************')
 print()

 __SCREAMING_SNAKE_CASE     =						input('Enter the first string: ').strip()
 __SCREAMING_SNAKE_CASE     =						input('Enter the second string: ').strip()

 print()
 print(f'The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}')
 print(f'The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}')
 print()
 print('*************** End of Testing Edit Distance DP Algorithm ***************')

def 							UpperCAmelCase		(       lowercase				):







				"""simple docstring"""



				if not isinstance(lowercase				,     lowercase				):
								raise ValueError('''Input must be an integer'''				)
				if input_num <= 0:
								raise ValueError('''Input must be positive'''				)
				return sum(
				    divisor for divisor in range(1				,     input_num // 2 + 1				) if input_num % divisor == 0				)


if __name__ == "__main__":
		import doctest

		doctest.testmod()