


'''simple docstring'''






import math


def 					_snake_case   (     A       )						->    bool:

							if 1 < number < 4:
														# 2 and 3 are primes
														return True
							elif number < 2 or number % 2 == 0 or number % 3 == 0:
														# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
														return False

							# All primes number are in format of 6k +/- 1
							for i in range(5 ,    int(math.sqrt(A       ) + 1       ) ,    6       ):
														if number % i == 0 or number % (i + 2) == 0:
																					return False
							return True


def 					_snake_case   (     A = 600851475143       )						->    int:

							try:
														lowerCAmelCase__          =	int(A       )
							except (TypeError, ValueError):
														raise TypeError('''Parameter n must be int or castable to int.'''       )
							if n <= 0:
														raise ValueError('''Parameter n must be greater than or equal to one.'''       )
							lowerCAmelCase__          =	0
							if is_prime(A       ):
														return n
							while n % 2 == 0:
														n //= 2
							if is_prime(A       ):
														return n
							for i in range(3 ,    int(math.sqrt(A       )       ) + 1 ,    2       ):
														if n % i == 0:
																					if is_prime(n // i       ):
																												lowerCAmelCase__          =	n // i
																												break
																					elif is_prime(A       ):
																												lowerCAmelCase__          =	i
							return max_number


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



'''simple docstring'''






from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

__UpperCAmelCase    				=							TypeVar('''T''')
__UpperCAmelCase    				=							TypeVar('''U''')




class 		a__				(							Generic[T, U]  ):





							'''simple docstring'''






							def __init__(		self					,    lowerCamelCase_					,    lowerCamelCase_   )       ->							Union[str, Any]:
														lowerCAmelCase__          =	key
														lowerCAmelCase__          =	val
														lowerCAmelCase__          =	0
														lowerCAmelCase__          =	None
														lowerCAmelCase__          =	None







							def __repr__(		self   )       ->							str:
														return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
														    self.key					,    self.val					,    self.freq					,    self.next is not None					,    self.prev is not None   )




class 		a__				(							Generic[T, U]  ):





							'''simple docstring'''






							def __init__(		self   )       ->							None:
														lowerCAmelCase__          =	DoubleLinkedListNode(lowerCamelCase_					,    lowerCamelCase_   )
														lowerCAmelCase__          =	DoubleLinkedListNode(lowerCamelCase_					,    lowerCamelCase_   )
														lowerCAmelCase__   ,					lowerCAmelCase__          =	self.rear, self.head







							def __repr__(		self   )       ->							str:
														lowerCAmelCase__          =	['''DoubleLinkedList''']
														lowerCAmelCase__          =	self.head
														while node.next is not None:
																					rep.append(str(lowerCamelCase_   )   )
																					lowerCAmelCase__          =	node.next
														rep.append(str(self.rear   )   )
														return ",\n    ".join(lowerCamelCase_   )







							def   __SCREAMING_SNAKE_CASE							(		self					,    lowerCamelCase_   )       ->							None:
														lowerCAmelCase__          =	self.rear.prev

														# All nodes other than self.head are guaranteed to have non-None previous
														assert previous is not None

														lowerCAmelCase__          =	node
														lowerCAmelCase__          =	previous
														lowerCAmelCase__          =	node
														lowerCAmelCase__          =	self.rear
														node.freq += 1
														self._position_node(lowerCamelCase_   )







							def   __SCREAMING_SNAKE_CASE							(		self					,    lowerCamelCase_   )       ->							None:

														while node.prev is not None and node.prev.freq > node.freq:
																					# swap node with previous node
																					lowerCAmelCase__          =	node.prev

																					lowerCAmelCase__          =	previous_node.prev
																					lowerCAmelCase__          =	node.prev
																					lowerCAmelCase__          =	previous_node
																					lowerCAmelCase__          =	node







							def   __SCREAMING_SNAKE_CASE							(		self					,    lowerCamelCase_   )       ->							DoubleLinkedListNode[T, U] | None:

														if node.prev is None or node.next is None:
																					return None

														lowerCAmelCase__          =	node.next
														lowerCAmelCase__          =	node.prev
														lowerCAmelCase__          =	None
														lowerCAmelCase__          =	None
														return node




class 		a__				(							Generic[T, U]  ):





							'''simple docstring'''






							lowercase__			:   dict[Callable[[T], U], LFUCache[T, U]]							=      {}







							def __init__(		self					,    lowerCamelCase_   )       ->							Any:
														lowerCAmelCase__          =	DoubleLinkedList()
														lowerCAmelCase__          =	capacity
														lowerCAmelCase__          =	0
														lowerCAmelCase__          =	0
														lowerCAmelCase__          =	0
														lowerCAmelCase__          =	{}







							def __repr__(		self   )       ->							str:
														return (
														    F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
														    F"""capacity={self.capacity}, current_size={self.num_keys})"""
														)







							def __contains__(		self					,    lowerCamelCase_   )       ->							bool:
														return key in self.cache







							def   __SCREAMING_SNAKE_CASE							(		self					,    lowerCamelCase_   )       ->							U | None:

														if key in self.cache:
																					self.hits += 1
																					lowerCAmelCase__          =	self.cache[key]
																					lowerCAmelCase__          =	self.list.remove(self.cache[key]   )
																					assert node == value_node

																					# node is guaranteed not None because it is in self.cache
																					assert node is not None
																					self.list.add(lowerCamelCase_   )
																					return node.val
														self.miss += 1
														return None







							def   __SCREAMING_SNAKE_CASE							(		self					,    lowerCamelCase_					,    lowerCamelCase_   )       ->							None:

														if key not in self.cache:
																					if self.num_keys >= self.capacity:
																												# delete first node when over capacity
																												lowerCAmelCase__          =	self.list.head.next

																												# guaranteed to have a non-None first node when num_keys > 0
																												# explain to type checker via assertions
																												assert first_node is not None
																												assert first_node.key is not None
																												assert self.list.remove(lowerCamelCase_   ) is not None
																												# first_node guaranteed to be in list

																												del self.cache[first_node.key]
																												self.num_keys -= 1
																					lowerCAmelCase__          =	DoubleLinkedListNode(lowerCamelCase_					,    lowerCamelCase_   )
																					self.list.add(self.cache[key]   )
																					self.num_keys += 1

														else:
																					lowerCAmelCase__          =	self.list.remove(self.cache[key]   )
																					assert node is not None  # node guaranteed to be in list
																					lowerCAmelCase__          =	value
																					self.list.add(lowerCamelCase_   )







							@classmethod
							def   __SCREAMING_SNAKE_CASE							(		cls					,    lowerCamelCase_ = 1_28   )       ->							Callable[[Callable[[T], U]], Callable[..., U]]:

														def cache_decorator_inner(lowerCamelCase_   ) -> Callable[..., U]:
																					def cache_decorator_wrapper(*lowerCamelCase_   ) -> U:
																												if func not in cls.decorator_function_to_instance_map:
																																			lowerCAmelCase__          =	LFUCache(lowerCamelCase_   )

																												lowerCAmelCase__          =	cls.decorator_function_to_instance_map[func].get(args[0]   )
																												if result is None:
																																			lowerCAmelCase__          =	func(*lowerCamelCase_   )
																																			cls.decorator_function_to_instance_map[func].put(args[0]					,    lowerCamelCase_   )
																												return result

																					def cache_info() -> LFUCache[T, U]:
																												return cls.decorator_function_to_instance_map[func]

																					setattr(lowerCamelCase_					,    '''cache_info'''					,    lowerCamelCase_   )  # noqa: B010

																					return cache_decorator_wrapper

														return cache_decorator_inner


if __name__ == "__main__":
		import doctest

		doctest.testmod()