


class 						lowerCamelCase_							:



					'''simple docstring'''







					def __init__(					self    ) ->      List[str]:







								'''simple docstring'''

								__lowercase			       = 0
								__lowercase			       = 0
								__lowercase			       = {}






					def A   (					self			,							snake_case_    ) ->      int:







								'''simple docstring'''

								if vertex not in self.adjacency:
											__lowercase			       = {}
											self.num_vertices += 1






					def A   (					self			,							snake_case_			,							snake_case_			,							snake_case_    ) ->      Dict:







								'''simple docstring'''

								self.add_vertex(snake_case_    )
								self.add_vertex(snake_case_    )

								if head == tail:
											return

								__lowercase			       = weight
								__lowercase			       = weight






					def A   (					self    ) ->      List[str]:







								'''simple docstring'''

								__lowercase			       = self.get_edges()
								for edge in edges:
											__lowercase       ,			__lowercase       ,			__lowercase			       = edge
											edges.remove((tail, head, weight)    )
								for i in range(len(snake_case_    )    ):
											__lowercase			       = list(edges[i]    )

								edges.sort(key=lambda snake_case_    : e[2]    )
								for i in range(len(snake_case_    ) - 1    ):
											if edges[i][2] >= edges[i + 1][2]:
														__lowercase			       = edges[i][2] + 1
								for edge in edges:
											__lowercase       ,			__lowercase       ,			__lowercase			       = edge
											__lowercase			       = weight
											__lowercase			       = weight






					def __str__(					self    ) ->      Dict:







								'''simple docstring'''

								__lowercase			       = ''''''
								for tail in self.adjacency:
											for head in self.adjacency[tail]:
														__lowercase			       = self.adjacency[head][tail]
														string += F'{head} -> {tail} == {weight}\n'
								return string.rstrip('''\n'''    )






					def A   (					self    ) ->      List[Any]:







								'''simple docstring'''

								__lowercase			       = []
								for tail in self.adjacency:
											for head in self.adjacency[tail]:
														output.append((tail, head, self.adjacency[head][tail])    )
								return output






					def A   (					self    ) ->      Optional[int]:







								'''simple docstring'''

								return self.adjacency.keys()






					@staticmethod
					def A   (					snake_case_=None			,							snake_case_=None    ) ->      Union[str, Any]:







								'''simple docstring'''

								__lowercase			       = Graph()
								if vertices is None:
											__lowercase			       = []
								if edges is None:
											__lowercase			       = []
								for vertex in vertices:
											g.add_vertex(snake_case_    )
								for edge in edges:
											g.add_edge(*snake_case_    )
								return g
					class 						lowerCamelCase_							:



										'''simple docstring'''







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







													'''simple docstring'''

													__lowercase			       = {}
													__lowercase			       = {}






										def __len__(					self    ) ->      int:







													'''simple docstring'''

													return len(self.parent    )






										def A   (					self			,							snake_case_    ) ->      Optional[int]:







													'''simple docstring'''

													if item in self.parent:
																return self.find(snake_case_    )

													__lowercase			       = item
													__lowercase			       = 0
													return item






										def A   (					self			,							snake_case_    ) ->      int:







													'''simple docstring'''

													if item not in self.parent:
																return self.make_set(snake_case_    )
													if item != self.parent[item]:
																__lowercase			       = self.find(self.parent[item]    )
													return self.parent[item]






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







													'''simple docstring'''

													__lowercase			       = self.find(snake_case_    )
													__lowercase			       = self.find(snake_case_    )

													if roota == roota:
																return roota

													if self.rank[roota] > self.rank[roota]:
																__lowercase			       = roota
																return roota

													if self.rank[roota] < self.rank[roota]:
																__lowercase			       = roota
																return roota

													if self.rank[roota] == self.rank[roota]:
																self.rank[roota] += 1
																__lowercase			       = roota
																return roota
													return None






					@staticmethod
					def A   (					snake_case_    ) ->      str:







								'''simple docstring'''

								__lowercase			       = graph.num_vertices

								__lowercase			       = Graph.UnionFind()
								__lowercase			       = []
								while num_components > 1:
											__lowercase			       = {}
											for vertex in graph.get_vertices():
														__lowercase			       = -1

											__lowercase			       = graph.get_edges()
											for edge in edges:
														__lowercase       ,			__lowercase       ,			__lowercase			       = edge
														edges.remove((tail, head, weight)    )
											for edge in edges:
														__lowercase       ,			__lowercase       ,			__lowercase			       = edge
														__lowercase			       = union_find.find(snake_case_    )
														__lowercase			       = union_find.find(snake_case_    )
														if seta != seta:
																	if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																				__lowercase			       = [head, tail, weight]

																	if cheap_edge[seta] == -1 or cheap_edge[seta][2] > weight:
																				__lowercase			       = [head, tail, weight]
											for vertex in cheap_edge:
														if cheap_edge[vertex] != -1:
																	__lowercase       ,			__lowercase       ,			__lowercase			       = cheap_edge[vertex]
																	if union_find.find(snake_case_    ) != union_find.find(snake_case_    ):
																				union_find.union(snake_case_			,							snake_case_    )
																				mst_edges.append(cheap_edge[vertex]    )
																				__lowercase			       = num_components - 1
								__lowercase			       = Graph.build(edges=snake_case_    )
								return mst






a			:			Any												=					[sum(int(c, 10) ** 2 for c in i.__str__()) for i in range(100000)]


def 		lowercase_	(  _UpperCamelCase	):


			'''simple docstring'''







			__lowercase			       = 0
			while number:
						# Increased Speed Slightly by checking every 5 digits together.
						sum_of_digits_squared += DIGITS_SQUARED[number % 10_00_00]
						number //= 10_00_00

			return sum_of_digits_squared


# There are 2 Chains made,
# One ends with 89 with the chain member 58 being the one which when declared first,
# there will be the least number of iterations for all the members to be checked.

# The other one ends with 1 and has only one element 1.

# So 58 and 1 are chosen to be declared at the starting.

# Changed dictionary to an array to quicken the solution
a			:			list[bool | None]												=					[None] * 10000000
a			:			int												=					True
a			:			Any												=					False


def 		lowercase_	(  _UpperCamelCase	):


			'''simple docstring'''







			if CHAINS[number - 1] is not None:
						return CHAINS[number - 1]  # type: ignore

			__lowercase			       = chain(next_number(_UpperCamelCase	)	)
			__lowercase			       = number_chain

			while number < 10_00_00_00:
						__lowercase			       = number_chain
						number *= 10

			return number_chain


def 		lowercase_	(  _UpperCamelCase = 10_00_00_00	):


			'''simple docstring'''







			for i in range(1							,      _UpperCamelCase	):
						if CHAINS[i] is None:
									chain(i + 1	)

			return CHAINS[:number].count(_UpperCamelCase	)


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	print(f'''{solution() = }''')


