






"""simple docstring"""



from __future__ import annotations

import sys
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    int						,   __snake_case     :    Tuple       ):





  '''simple docstring'''





  if abs(_UpperCAmelCase       ) == 1:
    return a, 0
  elif abs(_UpperCAmelCase       ) == 1:
    return 0, b

  lowercase				       =			a, b
  lowercase				       =			1, 0
  lowercase				       =			0, 1

  while remainder != 0:
    lowercase				       =			old_remainder // remainder
    lowercase				       =			remainder, old_remainder - quotient * remainder
    lowercase				       =			coeff_a, old_coeff_a - quotient * coeff_a
    lowercase				       =			coeff_b, old_coeff_b - quotient * coeff_b

  # sign correction for negative numbers
  if a < 0:
    lowercase				       =			-old_coeff_a
  if b < 0:
    lowercase				       =			-old_coeff_b

  return old_coeff_a, old_coeff_b
def 		_SCREAMING_SNAKE_CASE					(       ):





  '''simple docstring'''





  if len(sys.argv       ) < 3:
    print('2 integer arguments required'       )
    return 1
  lowercase				       =			int(sys.argv[1]       )
  lowercase				       =			int(sys.argv[2]       )
  print(extended_euclidean_algorithm(_UpperCAmelCase						,   _UpperCAmelCase       )       )
  return 0


if __name__ == "__main__":
    raise SystemExit(main())







"""simple docstring"""




from __future__ import annotations


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      lowercase	:   Optional[Any]											= [0] * max_one

      for i in range(0						,   _UpperCAmelCase					):
            lowercase	:   List[Any]											= i

      for i in range(2						,   _UpperCAmelCase					):
            if totients[i] == i:
                  for j in range(_UpperCAmelCase						,   _UpperCAmelCase						,   _UpperCAmelCase					):
                        totients[j] -= totients[j] // i

      return totients


def 	lowercase__  (      _UpperCAmelCase						,   _UpperCAmelCase					)  ->      bool:






      '''simple docstring'''


      return sorted(str(_UpperCAmelCase					)					) == sorted(str(_UpperCAmelCase					)					)


def 	lowercase__  (      _UpperCAmelCase = 10_00_00_00					)  ->      int:






      '''simple docstring'''


      lowercase	:   Union[str, Any]											= 1  # i
      lowercase	:   Any											= 0  # φ(i)
      lowercase	:   int											= get_totients(max_n + 1					)

      for i in range(2						,   max_n + 1					):
            lowercase	:   Any											= totients[i]

            if i * min_denominator < min_numerator * t and has_same_digits(_UpperCAmelCase						,   _UpperCAmelCase					):
                  lowercase	:   List[Any]											= i
                  lowercase	:   Optional[Any]											= t

      return min_numerator


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