






from __future__ import annotations

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

a_							=    TypeVar('''T''')
a_							=    TypeVar('''U''')


class      lowercase__     (			Generic[T, U]	):

	def __init__(							self		,    __UpperCAmelCase		,    __UpperCAmelCase       )->					Optional[Any]:







							'''simple docstring'''





							lowerCAmelCase__       =						key
							lowerCAmelCase__       =						val
							lowerCAmelCase__       =						None
							lowerCAmelCase__       =						None


	def __repr__(							self       )->					Union[str, Any]:







							'''simple docstring'''





							return (
							    F"Node: key: {self.key}, val: {self.val}, "
							    F"has next: {bool(self.next       )}, has prev: {bool(self.prev       )}"
							)





class      lowercase__     (			Generic[T, U]	):

	def __init__(							self       )->					Tuple:







							'''simple docstring'''





							lowerCAmelCase__       =						DoubleLinkedListNode(__A		,    __A       )
							lowerCAmelCase__       =						DoubleLinkedListNode(__A		,    __A       )
							lowerCAmelCase__       =						self.rear, self.head

	def __repr__(							self       )->					Union[str, Any]:







							'''simple docstring'''





							lowerCAmelCase__       =						["DoubleLinkedList"]
							lowerCAmelCase__       =						self.head
							while node.next is not None:
													rep.append(str(__A       )       )
													lowerCAmelCase__       =						node.next
							rep.append(str(self.rear       )       )
							return ",\n    ".join(__A       )

	def 		UpperCAmelCase  (							self		,    __UpperCAmelCase       )->					Optional[int]:







							'''simple docstring'''





							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


	def 		UpperCAmelCase  (							self		,    __UpperCAmelCase       )->					str:







							'''simple docstring'''





							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      lowercase__     (			Generic[T, U]	):
	a_         ={}

	def __init__(							self		,    __UpperCAmelCase       )->					Optional[int]:







							'''simple docstring'''





							lowerCAmelCase__       =						DoubleLinkedList()
							lowerCAmelCase__       =						capacity
							lowerCAmelCase__       =						0
							lowerCAmelCase__       =						0
							lowerCAmelCase__       =						0
							lowerCAmelCase__       =						{}

	def __repr__(							self       )->					Dict:







							'''simple docstring'''





							return (
							    F"CacheInfo(hits={self.hits}, misses={self.miss}, "
							    F"capacity={self.capacity}, current size={self.num_keys})"
							)

	def __contains__(							self		,    __UpperCAmelCase       )->					Any:







							'''simple docstring'''





							return key in self.cache

	def 		UpperCAmelCase  (							self		,    __UpperCAmelCase       )->					Any:







							'''simple docstring'''





							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(__A       )
													return node.val
							self.miss += 1
							return None

	def 		UpperCAmelCase  (							self		,    __UpperCAmelCase		,    __UpperCAmelCase       )->					Any:







							'''simple docstring'''





							if key not in self.cache:
													if self.num_keys >= self.capacity:
																			# delete first node (oldest) 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(__A       ) is not None
																			)  # node guaranteed to be in list assert node.key is not None

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

							else:
													# bump node to the end of the list, update value
													lowerCAmelCase__       =						self.list.remove(self.cache[key]       )
													assert node is not None  # node guaranteed to be in list
													lowerCAmelCase__       =						value
													self.list.add(__A       )


	@classmethod
	def 		UpperCAmelCase  (							cls		,    __UpperCAmelCase = 128       )->					Any:







							'''simple docstring'''





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

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

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

													setattr(__A		,    "cache_info"		,    __A       )  # noqa: B010

													return cache_decorator_wrapper

							return cache_decorator_inner


if __name__ == "__main__":
	import doctest

	doctest.testmod()














from __future__ import annotations

from collections.abc import Generator


def        _a  (     ) ->   Generator[int, None, None]:
						"""simple docstring"""







						lowerCAmelCase__       =						{}
						lowerCAmelCase__       =						2
						while True:
												lowerCAmelCase__       =						factor_map.pop(UpperCamelCase_    ,   UpperCamelCase_   )
												if factor:
																		lowerCAmelCase__       =						factor + prime
																		while x in factor_map:
																								x += factor
																		lowerCAmelCase__       =						factor
												else:
																		lowerCAmelCase__       =						prime
																		yield prime
												prime += 1


def        _a  (     UpperCamelCase_					:				float = 1e1_0   ) ->   int:
						"""simple docstring"""







						lowerCAmelCase__       =						sieve()

						lowerCAmelCase__       =						1
						while True:
												lowerCAmelCase__       =						next(UpperCamelCase_   )
												if (2 * prime * n) > limit:
																		return n
												# Ignore the next prime as the reminder will be 2.
												next(UpperCamelCase_   )
												n += 2


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






