


'''simple docstring'''






import math
import unittest






def 	_A				(lowerCAmelCase__  :int		)   ->  bool:




     '''simple docstring'''



     assert isinstance(lowerCAmelCase__				,						lowerCAmelCase__		) and (
         number >= 0
     ), "'number' must been an int and positive"

     if 1 < number < 4:
          # 2 and 3 are primes
          return True
     elif number < 2 or number % 2 == 0 or number % 3 == 0:
          # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
          return False

     # All primes number are in format of 6k +/- 1
     for i in range(5				,						int(math.sqrt(lowerCAmelCase__		) + 1		)				,						6		):
          if number % i == 0 or number % (i + 2) == 0:
               return False
     return True




class  a     (     unittest.TestCase       ):
 def 							__UpperCAmelCase		( self						)					->							Optional[Any]:
      self.assertTrue(is_prime(2						)						)
      self.assertTrue(is_prime(3						)						)
      self.assertTrue(is_prime(5						)						)
      self.assertTrue(is_prime(7						)						)
      self.assertTrue(is_prime(11						)						)
      self.assertTrue(is_prime(13						)						)
      self.assertTrue(is_prime(17						)						)
      self.assertTrue(is_prime(19						)						)
      self.assertTrue(is_prime(23						)						)
      self.assertTrue(is_prime(29						)						)




 def 							__UpperCAmelCase		( self						)					->							int:
      with self.assertRaises(__magic_name__						):
           is_prime(-19						)
      self.assertFalse(
          is_prime(0						)      ,				'Zero doesn\'t have any positive factors, primes must have exactly two.'      ,				)
      self.assertFalse(
          is_prime(1						)      ,				'One only has 1 positive factor, primes must have exactly two.'      ,				)
      self.assertFalse(is_prime(2 * 2						)						)
      self.assertFalse(is_prime(2 * 3						)						)
      self.assertFalse(is_prime(3 * 3						)						)
      self.assertFalse(is_prime(3 * 5						)						)
      self.assertFalse(is_prime(3 * 5 * 7						)						)


if __name__ == "__main__":
 unittest.main()





'''simple docstring'''






class  a     :
 def __init__( self						)					->							List[Any]:
      _a			      =							''
      _a			      =							''
      _a			      =							[]
 def 							__UpperCAmelCase		( self      ,				__magic_name__      ,				__magic_name__						)					->							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]:
                _a			      =							self.__min_dist_top_down_dp(m - 1      ,				n - 1						)
           else:
                _a			      =							self.__min_dist_top_down_dp(__magic_name__      ,				n - 1						)
                _a			      =							self.__min_dist_top_down_dp(m - 1      ,				__magic_name__						)
                _a			      =							self.__min_dist_top_down_dp(m - 1      ,				n - 1						)
                _a			      =							1 + min(__magic_name__      ,				__magic_name__      ,				__magic_name__						)

           return self.dp[m][n]
 def 							__UpperCAmelCase		( self      ,				__magic_name__      ,				__magic_name__						)					->							int:
      _a			      =							worda
      _a			      =							worda
      _a			      =							[[-1 for _ in range(len(__magic_name__						)						)] for _ in range(len(__magic_name__						)						)]

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




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


if __name__ == "__main__":
 a_					:    Dict          =    EditDistance()

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

 a_					:    Tuple          =    input("Enter the first string: ").strip()
 a_					:    Dict          =    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 ***************")

