
"""simple docstring"""







from __future__ import annotations
def        __lowerCAmelCase							(_UpperCamelCase						):
	if not list_of_ints:
		return []

	if min(_UpperCamelCase						) < 0:
		raise ValueError('All numbers must be positive'						)

	__lowerCAmelCase     :		List[Any]		     = max(len(bin(_UpperCamelCase						)[2:]						) for x in list_of_ints						)
	return _msd_radix_sort(_UpperCamelCase			,    _UpperCamelCase						)
def        __lowerCAmelCase							(_UpperCamelCase			,    _UpperCamelCase						):
	if bit_position == 0 or len(_UpperCamelCase						) in [0, 1]:
		return list_of_ints

	__lowerCAmelCase     :		int		     = []
	__lowerCAmelCase     :		Union[str, Any]		     = []
	# Split numbers based on bit at bit_position from the right
	for number in list_of_ints:
		if (number >> (bit_position - 1)) & 1:
			# number has a one at bit bit_position
			ones.append(_UpperCamelCase						)
		else:
			# number has a zero at bit bit_position
			zeros.append(_UpperCamelCase						)

    # recursively split both lists further
	__lowerCAmelCase     :		Union[str, Any]		     = _msd_radix_sort(_UpperCamelCase			,    bit_position - 1						)
	__lowerCAmelCase     :		Dict		     = _msd_radix_sort(_UpperCamelCase			,    bit_position - 1						)

	# recombine lists
	__lowerCAmelCase     :		int		     = zeros
	res.extend(_UpperCamelCase						)

	return res
def        __lowerCAmelCase							(_UpperCamelCase						):
	__lowerCAmelCase     :		List[Any]		     = len(_UpperCamelCase						)
	if not list_of_ints or length == 1:
		return

	if min(_UpperCamelCase						) < 0:
		raise ValueError('All numbers must be positive'						)

	__lowerCAmelCase     :		Tuple		     = max(len(bin(_UpperCamelCase						)[2:]						) for x in list_of_ints						)
	_msd_radix_sort_inplace(_UpperCamelCase			,    _UpperCamelCase			,    0			,    _UpperCamelCase						)
def        __lowerCAmelCase							(_UpperCamelCase			,    _UpperCamelCase			,    _UpperCamelCase			,    _UpperCamelCase						):
	if bit_position == 0 or end_index - begin_index <= 1:
		return

	bit_position -= 1

	__lowerCAmelCase     :		str		     = begin_index
	__lowerCAmelCase     :		Tuple		     = end_index - 1
	while i <= j:
		__lowerCAmelCase     :		str		     = False
		if not (list_of_ints[i] >> bit_position) & 1:
			# found zero at the beginning
			i += 1
			__lowerCAmelCase     :		Tuple		     = True
		if (list_of_ints[j] >> bit_position) & 1:
			# found one at the end
			j -= 1
			__lowerCAmelCase     :		List[Any]		     = True

		if changed:
			continue

		__lowerCAmelCase     ,  __lowerCAmelCase     :		Tuple		     = list_of_ints[j], list_of_ints[i]
		j -= 1
		if j != i:
			i += 1

	_msd_radix_sort_inplace(_UpperCamelCase			,    _UpperCamelCase			,    _UpperCamelCase			,    _UpperCamelCase						)
	_msd_radix_sort_inplace(_UpperCamelCase			,    _UpperCamelCase			,    _UpperCamelCase			,    _UpperCamelCase						)


if __name__ == "__main__":
							import doctest

							doctest.testmod()

"""simple docstring"""







def        __lowerCAmelCase							(_UpperCamelCase = 10**6						):

	if n <= 0:
		raise ValueError('Please enter an integer greater than 0'						)

	__lowerCAmelCase     :		Optional[Any]		     = list(range(n + 1						)						)
	for number in range(2			,    n + 1						):
		if phi[number] == number:
			phi[number] -= 1
			for multiple in range(number * 2			,    n + 1			,    _UpperCamelCase						):
				__lowerCAmelCase     :		Tuple		     = (phi[multiple] // number) * (number - 1)

	__lowerCAmelCase     :		Any		     = 1
	for number in range(1			,    n + 1						):
		if (answer / phi[answer]) < (number / phi[number]):
			__lowerCAmelCase     :		List[Any]		     = number

	return answer


if __name__ == "__main__":
							print(solution())