





from __future__ import annotations

from typing import Any

class        __SCREAMING_SNAKE_CASE					:






							def __init__(						self  , __lowerCAmelCase  ):
														UpperCamelCase__				     =			num_of_nodes
														UpperCamelCase__				     =			[]
														UpperCamelCase__				     =			{}






							def 				_lowerCamelCase		(						self  , __lowerCAmelCase  , __lowerCAmelCase  , __lowerCAmelCase  ):
														self.m_edges.append([u_node, v_node, weight]  )






							def 				_lowerCamelCase		(						self  , __lowerCAmelCase  ):

														if self.m_component[u_node] == u_node:
																					return u_node
														return self.find_component(self.m_component[u_node]  )






							def 				_lowerCamelCase		(						self  , __lowerCAmelCase  ):

														if self.m_component[u_node] != u_node:
																					for k in self.m_component:
																												UpperCamelCase__				     =			self.find_component(__lowerCAmelCase  )






							def 				_lowerCamelCase		(						self  , __lowerCAmelCase  , __lowerCAmelCase  , __lowerCAmelCase  ):

														if component_size[u_node] <= component_size[v_node]:
																					UpperCamelCase__				     =			v_node
																					component_size[v_node] += component_size[u_node]
																					self.set_component(__lowerCAmelCase  )

														elif component_size[u_node] >= component_size[v_node]:
																					UpperCamelCase__				     =			self.find_component(__lowerCAmelCase  )
																					component_size[u_node] += component_size[v_node]
																					self.set_component(__lowerCAmelCase  )







							def 				_lowerCamelCase		(						self  ):
														UpperCamelCase__				     =			[]
														UpperCamelCase__				     =			0

														UpperCamelCase__				     =			[-1] * self.m_num_of_nodes

														# A list of components (initialized to all of the nodes)
														for node in range(self.m_num_of_nodes  ):
																					self.m_component.update({node: node}  )
																					component_size.append(1  )

														UpperCamelCase__				     =			self.m_num_of_nodes

														while num_of_components > 1:
																					for edge in self.m_edges:
																												UpperCamelCase__     ,     UpperCamelCase__     ,     UpperCamelCase__				     =			edge

																												UpperCamelCase__				     =			self.m_component[u]
																												UpperCamelCase__				     =			self.m_component[v]

																												if u_component != v_component:

																																			for component in (u_component, v_component):
																																										if (
																																										    minimum_weight_edge[component] == -1
																																										    or minimum_weight_edge[component][2] > w
																																										):
																																																	UpperCamelCase__				     =			[u, v, w]

																					for edge in minimum_weight_edge:
																												if isinstance(__lowerCAmelCase  , __lowerCAmelCase  ):
																																			UpperCamelCase__     ,     UpperCamelCase__     ,     UpperCamelCase__				     =			edge

																																			UpperCamelCase__				     =			self.m_component[u]
																																			UpperCamelCase__				     =			self.m_component[v]

																																			if u_component != v_component:
																																										mst_weight += w
																																										self.union(__lowerCAmelCase  , __lowerCAmelCase  , __lowerCAmelCase  )
																																										print(f"""Added edge [{u} - {v}]\nAdded weight: {w}\n"""  )
																																										num_of_components -= 1

																					UpperCamelCase__				     =			[-1] * self.m_num_of_nodes
														print(f"""The total weight of the minimal spanning tree is: {mst_weight}"""  )






def     _UpperCamelCase     ():






							"""simple docstring"""







if __name__ == "__main__":
					import doctest

					doctest.testmod()











import math





def     _UpperCamelCase     (a__   :int       ):






							"""simple docstring"""





							UpperCamelCase__				     =			[True] * n
							UpperCamelCase__				     =			False
							UpperCamelCase__				     =			False
							UpperCamelCase__				     =			True

							for i in range(3   ,			int(n**0.5 + 1       )   ,			2       ):
														UpperCamelCase__				     =			i * 2
														while index < n:
																					UpperCamelCase__				     =			False
																					UpperCamelCase__				     =			index + i

							UpperCamelCase__				     =			[2]

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

							return primes





def     _UpperCamelCase     (a__   :int = 9999_6666_3333       ):






							"""simple docstring"""





							UpperCamelCase__				     =			math.floor(math.sqrt(a__       )       ) + 100
							UpperCamelCase__				     =			prime_sieve(a__       )

							UpperCamelCase__				     =			0
							UpperCamelCase__				     =			0
							UpperCamelCase__				     =			primes[prime_index]

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

														UpperCamelCase__				     =			last_prime**2
														UpperCamelCase__				     =			next_prime**2

														# Get numbers divisible by lps(current)
														UpperCamelCase__				     =			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)
														UpperCamelCase__				     =			upper_bound - next_prime
														while current > lower_bound:
																					matches_sum += current
																					current -= next_prime

														# Remove the numbers divisible by both ups and lps
														UpperCamelCase__				     =			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
														UpperCamelCase__				     =			next_prime
														prime_index += 1

							return matches_sum


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




