






import numpy as np






def    UpperCamelCase__  (   UpperCAmelCase     )     ->		int:







							"""simple docstring"""





							_a		,					_a  :    Dict			=						a.shape
							_a  :    Union[str, Any]			=						min(UpperCAmelCase    ,	UpperCAmelCase     )
							_a  :    Optional[int]			=						np.eye(UpperCAmelCase     )
							_a  :    Optional[Any]			=						a.copy()

							for k in range(t - 1     ):
														# select a column of modified matrix A':
														_a  :    Any			=						r[k:, [k]]
														# construct first basis vector
														_a  :    Any			=						np.zeros_like(UpperCAmelCase     )
														_a  :    Optional[Any]			=						1.0
														# determine scaling factor
														_a  :    Optional[Any]			=						np.linalg.norm(UpperCAmelCase     )
														# construct vector v for Householder reflection
														_a  :    str			=						x + np.sign(x[0]     ) * alpha * ea
														v /= np.linalg.norm(UpperCAmelCase     )

														# construct the Householder matrix
														_a  :    Any			=						np.eye(m - k     ) - 2.0 * v @ v.T
														# pad with ones and zeros as necessary
														_a  :    Optional[Any]			=						np.block([[np.eye(UpperCAmelCase     ), np.zeros((k, m - k)     )], [np.zeros((m - k, k)     ), q_k]]     )

														_a  :    Union[str, Any]			=						q @ q_k.T
														_a  :    List[Any]			=						q_k @ r

							return q, r


if __name__ == "__main__":
						import doctest

						doctest.testmod()







from __future__ import annotations






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







							"""simple docstring"""





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

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







							"""simple docstring"""





							return sorted(str(UpperCAmelCase     )     ) == sorted(str(UpperCAmelCase     )     )






def    UpperCamelCase__  (   UpperCAmelCase = 10000000     )     ->		int:







							"""simple docstring"""





							_a  :    List[Any]			=						1  # i
							_a  :    Any			=						0  # φ(i)
							_a  :    Tuple			=						get_totients(max_n + 1     )

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

														if i * min_denominator < min_numerator * t and has_same_digits(UpperCAmelCase    ,	UpperCAmelCase     ):
																					_a  :    Any			=						i
																					_a  :    Union[str, Any]			=						t

							return min_numerator


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