

"""simple docstring"""




class 	UpperCAmelCase__		:






  """simple docstring"""


  def __init__(							self						:		Optional[int] )		->							Optional[int]:
       SCREAMING_SNAKE_CASE__   =   ''
       SCREAMING_SNAKE_CASE__   =   ''
       SCREAMING_SNAKE_CASE__   =   []






  def 				lowercase_		(							self						:		str     ,       __lowerCamelCase						:		str     ,       __lowerCamelCase						:		Tuple )		->							int:

       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]:
                 SCREAMING_SNAKE_CASE__   =   self.__min_dist_top_down_dp(m - 1     ,       n - 1 )
            else:
                 SCREAMING_SNAKE_CASE__   =   self.__min_dist_top_down_dp(__lowerCamelCase     ,       n - 1 )
                 SCREAMING_SNAKE_CASE__   =   self.__min_dist_top_down_dp(m - 1     ,       __lowerCamelCase )
                 SCREAMING_SNAKE_CASE__   =   self.__min_dist_top_down_dp(m - 1     ,       n - 1 )
                 SCREAMING_SNAKE_CASE__   =   1 + min(__lowerCamelCase     ,       __lowerCamelCase     ,       __lowerCamelCase )

            return self.dp[m][n]






  def 				lowercase_		(							self						:		int     ,       __lowerCamelCase						:		List[str]     ,       __lowerCamelCase						:		Union[str, Any] )		->							int:
       SCREAMING_SNAKE_CASE__   =   worda
       SCREAMING_SNAKE_CASE__   =   worda
       SCREAMING_SNAKE_CASE__   =   [[-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 				lowercase_		(							self						:		Any     ,       __lowerCamelCase						:		Any     ,       __lowerCamelCase						:		Union[str, Any] )		->							int:
       SCREAMING_SNAKE_CASE__   =   worda
       SCREAMING_SNAKE_CASE__   =   worda
       SCREAMING_SNAKE_CASE__   =   len(__lowerCamelCase )
       SCREAMING_SNAKE_CASE__   =   len(__lowerCamelCase )
       SCREAMING_SNAKE_CASE__   =   [[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
                      SCREAMING_SNAKE_CASE__   =   j
                 elif j == 0:  # second string is empty
                      SCREAMING_SNAKE_CASE__   =   i
                 elif worda[i - 1] == worda[j - 1]:  # last characters are equal
                      SCREAMING_SNAKE_CASE__   =   self.dp[i - 1][j - 1]
                 else:
                      SCREAMING_SNAKE_CASE__   =   self.dp[i][j - 1]
                      SCREAMING_SNAKE_CASE__   =   self.dp[i - 1][j]
                      SCREAMING_SNAKE_CASE__   =   self.dp[i - 1][j - 1]
                      SCREAMING_SNAKE_CASE__   =   1 + min(__lowerCamelCase     ,       __lowerCamelCase     ,       __lowerCamelCase )
       return self.dp[m][n]


if __name__ == "__main__":
       _SCREAMING_SNAKE_CASE					:  int             =      EditDistance()

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

       _SCREAMING_SNAKE_CASE					:  str             =      input('''Enter the first string: ''').strip()
       _SCREAMING_SNAKE_CASE					:  int             =      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_       (						_A    ):





     '''simple docstring'''




     if divisor % 5 == 0 or divisor % 2 == 0:
          return 0
     SCREAMING_SNAKE_CASE__   =   1
     SCREAMING_SNAKE_CASE__   =   1
     while repunit:
          SCREAMING_SNAKE_CASE__   =   (10 * repunit + 1) % divisor
          repunit_index += 1
     return repunit_index
def     UpperCAmelCase_       (						_A = 1_00_00_00    ):





     '''simple docstring'''




     SCREAMING_SNAKE_CASE__   =   limit - 1
     if divisor % 2 == 0:
          divisor += 1
     while least_divisible_repunit(_A    ) <= limit:
          divisor += 2
     return divisor


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


