





from __future__ import annotations
def 			__UpperCamelCase				(			lowercase__	:       int		)	->      list[int]:
    '''simple docstring'''





    lowerCAmelCase_					:	Tuple						=   [0] * max_one

    for i in range(0		,    lowercase__		):
        lowerCAmelCase_					:	Any						=   i

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

    return totients
def 			__UpperCamelCase				(			lowercase__	:       int		,    lowercase__	:       int		)	->      bool:
    '''simple docstring'''





    return sorted(str(lowercase__		)		) == sorted(str(lowercase__		)		)
def 			__UpperCamelCase				(			lowercase__	:       int = 10000000		)	->      int:
    '''simple docstring'''





    lowerCAmelCase_					:	str						=   1  # i
    lowerCAmelCase_					:	str						=   0  # φ(i)
    lowerCAmelCase_					:	Tuple						=   get_totients(max_n + 1		)

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

        if i * min_denominator < min_numerator * t and has_same_digits(lowercase__		,    lowercase__		):
            lowerCAmelCase_					:	Optional[Any]						=   i
            lowerCAmelCase_					:	Any						=   t

    return min_numerator


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











import math
def 			__UpperCamelCase				(			lowercase__	:       int		)	->      list:
    '''simple docstring'''





    if n <= 0:
        raise ValueError("""Only positive integers have prime factors"""		)
    lowerCAmelCase_					:	str						=   []
    while n % 2 == 0:
        pf.append(2		)
        lowerCAmelCase_					:	str						=   int(n / 2		)
    for i in range(3		,    int(math.sqrt(lowercase__		)		) + 1		,    2		):
        while n % i == 0:
            pf.append(lowercase__		)
            lowerCAmelCase_					:	List[Any]						=   int(n / i		)
    if n > 2:
        pf.append(lowercase__		)
    return pf
def 			__UpperCamelCase				(			lowercase__	:       int		)	->      int:
    '''simple docstring'''





    if n <= 0:
        raise ValueError("""Only positive numbers are accepted"""		)
    lowerCAmelCase_					:	Union[str, Any]						=   1
    lowerCAmelCase_					:	str						=   1
    while n % 2 == 0:
        temp += 1
        lowerCAmelCase_					:	Optional[Any]						=   int(n / 2		)
    div *= temp
    for i in range(3		,    int(math.sqrt(lowercase__		)		) + 1		,    2		):
        lowerCAmelCase_					:	Tuple						=   1
        while n % i == 0:
            temp += 1
            lowerCAmelCase_					:	Any						=   int(n / i		)
        div *= temp
    if n > 1:
        div *= 2
    return div
def 			__UpperCamelCase				(			lowercase__	:       int		)	->      int:
    '''simple docstring'''





    if n <= 0:
        raise ValueError("""Only positive numbers are accepted"""		)
    lowerCAmelCase_					:	Tuple						=   1
    lowerCAmelCase_					:	str						=   1
    while n % 2 == 0:
        temp += 1
        lowerCAmelCase_					:	Optional[int]						=   int(n / 2		)
    if temp > 1:
        s *= (2**temp - 1) / (2 - 1)
    for i in range(3		,    int(math.sqrt(lowercase__		)		) + 1		,    2		):
        lowerCAmelCase_					:	int						=   1
        while n % i == 0:
            temp += 1
            lowerCAmelCase_					:	Any						=   int(n / i		)
        if temp > 1:
            s *= (i**temp - 1) / (i - 1)
    return int(lowercase__		)
def 			__UpperCamelCase				(			lowercase__	:       int		)	->      int:
    '''simple docstring'''





    lowerCAmelCase_					:	str						=   n
    for x in set(prime_factors(lowercase__		)		):
        s *= (x - 1) / x
    return int(lowercase__		)


if __name__ == "__main__":
  import doctest

  doctest.testmod()


