




"""simple docstring"""






import math







def      _snake_case			(				lowercase__		):
				_lowerCamelCase     :			Any    =    [True] * n
				_lowerCamelCase     :			List[Any]    =    False
				_lowerCamelCase     :			Optional[int]    =    False
				_lowerCamelCase     :			Optional[int]    =    True

				for i in range(3							,    int(n**0.5 + 1		)							,    2		):
								_lowerCamelCase     :			Union[str, Any]    =    i * 2
								while index < n:
												_lowerCamelCase     :			List[Any]    =    False
												_lowerCamelCase     :			str    =    index + i

				_lowerCamelCase     :			Any    =    [2]

				for i in range(3							,    lowercase__							,    2		):
								if is_prime[i]:
												primes.append(lowercase__		)

				return primes







def      _snake_case			(				lowercase__ = 999966663333		):
				_lowerCamelCase     :			Tuple    =    math.floor(math.sqrt(lowercase__		)		) + 100
				_lowerCamelCase     :			Optional[int]    =    prime_sieve(lowercase__		)

				_lowerCamelCase     :			List[Any]    =    0
				_lowerCamelCase     :			Optional[int]    =    0
				_lowerCamelCase     :			Tuple    =    primes[prime_index]

				while (last_prime**2) <= limit:
								_lowerCamelCase     :			List[str]    =    primes[prime_index + 1]

								_lowerCamelCase     :			Dict    =    last_prime**2
								_lowerCamelCase     :			int    =    next_prime**2

								# Get numbers divisible by lps(current)
								_lowerCamelCase     :			Any    =    lower_bound + last_prime
								while upper_bound > current <= limit:
												matches_sum += current
												current += last_prime

								# Reset the upper_bound
								while (upper_bound - next_prime) > limit:
												upper_bound -= next_prime

								# Add the numbers divisible by ups(current)
								_lowerCamelCase     :			str    =    upper_bound - next_prime
								while current > lower_bound:
												matches_sum += current
												current -= next_prime

								# Remove the numbers divisible by both ups and lps
								_lowerCamelCase     :			int    =    0
								while upper_bound > current <= limit:
												if current <= lower_bound:
																# Increment the current number
																current += last_prime * next_prime
																continue

												if current > limit:
																break

												# Remove twice since it was added by both ups and lps
												matches_sum -= current * 2

												# Increment the current number
												current += last_prime * next_prime

								# Setup for next pair
								_lowerCamelCase     :			str    =    next_prime
								prime_index += 1

				return matches_sum


if __name__ == "__main__":
			print(solution())
'''simple docstring'''




def 				snake_case__							(			_A:					int      ,   _A:					int )    ->	int:

		'''simple docstring'''


		while a != 0:
				lowerCAmelCase					,     lowerCAmelCase   					=  b % a, a
		return b






def 				snake_case__							(			_A:					int      ,   _A:					int )    ->	int:

		'''simple docstring'''


		if gcd(_A      ,   _A ) != 1:
				lowerCAmelCase   					=  f"mod inverse of {a!r} and {m!r} does not exist"
				raise ValueError(_A )
		lowerCAmelCase					,     lowerCAmelCase					,     lowerCAmelCase   					=  1, 0, a
		lowerCAmelCase					,     lowerCAmelCase					,     lowerCAmelCase   					=  0, 1, m
		while va != 0:
				lowerCAmelCase   					=  ua // va
				lowerCAmelCase					,     lowerCAmelCase					,     lowerCAmelCase					,     lowerCAmelCase					,     lowerCAmelCase					,     lowerCAmelCase   					=  (ua - q * va), (ua - q * va), (ua - q * va), va, va, va
		return ua % m




