
'''simple docstring'''





from __future__ import annotations





def     snake_case							(						UpperCAmelCase		)->     list[int]:







      """simple docstring"""
      __A    		=     [0] * max_one

      for i in range(0 ,					UpperCAmelCase		):
            __A    		=     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     snake_case							(						UpperCAmelCase ,					UpperCAmelCase		)->     bool:







      """simple docstring"""
      return sorted(str(UpperCAmelCase		)		) == sorted(str(UpperCAmelCase		)		)





def     snake_case							(						UpperCAmelCase = 1_0_0_0_0_0_0_0		)->     int:







      """simple docstring"""
      __A    		=     1  # i
      __A    		=     0  # φ(i)
      __A    		=     get_totients(max_n + 1		)

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

            if i * min_denominator < min_numerator * t and has_same_digits(UpperCAmelCase ,					UpperCAmelCase		):
                  __A    		=     i
                  __A    		=     t

      return min_numerator


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








'''simple docstring'''





from __future__ import annotations





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase		)->     tuple[float, float]:







      """simple docstring"""
      assert (
          c % greatest_common_divisor(UpperCAmelCase ,					UpperCAmelCase		) == 0
      )  # greatest_common_divisor(a,b) function implemented below
      ((__A)		, (__A)		, (__A))    		=     extended_gcd(UpperCAmelCase ,					UpperCAmelCase		)  # extended_gcd(a,b) function implemented below
      __A    		=     c / d
      return (r * x, r * y)





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase = 2		)->     None:







      """simple docstring"""
      ((__A)		, (__A))    		=     diophantine(UpperCAmelCase ,					UpperCAmelCase ,					UpperCAmelCase		)  # Initial value
      __A    		=     greatest_common_divisor(UpperCAmelCase ,					UpperCAmelCase		)
      __A    		=     a // d
      __A    		=     b // d

      for i in range(UpperCAmelCase		):
            __A    		=     xa + i * q
            __A    		=     ya - i * p
            print(UpperCAmelCase ,					UpperCAmelCase		)





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase		)->     int:







      """simple docstring"""
      if a < b:
            __A		, __A    		=     b, a

      while a % b != 0:
            __A		, __A    		=     b, a % b

      return b





def     snake_case							(						UpperCAmelCase ,					UpperCAmelCase		)->     tuple[int, int, int]:







      """simple docstring"""
      assert a >= 0 and b >= 0

      if b == 0:
            __A		, __A		, __A    		=     a, 1, 0
      else:
            ((__A)		, (__A)		, (__A))    		=     extended_gcd(UpperCAmelCase ,					a % b		)
            __A    		=     q
            __A    		=     p - q * (a // b)

      assert a % d == 0 and b % d == 0
      assert d == a * x + b * y

      return (d, x, y)


if __name__ == "__main__":
 from doctest import testmod

 testmod(name="diophantine", verbose=True)
 testmod(name="diophantine_all_soln", verbose=True)
 testmod(name="extended_gcd", verbose=True)
 testmod(name="greatest_common_divisor", verbose=True)






