


"""simple docstring"""




from collections import deque

def        lowercase							(		lowerCAmelCase__ :     str			) ->      List[str]:
		__a           =			len(lowerCAmelCase__			)
		__a           =			deque()
		__a           =			[False for _ in range(lowerCAmelCase__			)]
		__a           =			[-1 for _ in range(lowerCAmelCase__			)]
		__a           =			index_of[:]

		def strong_connect(lowerCAmelCase__ :     Optional[Any]    ,					lowerCAmelCase__ :     Union[str, Any]    ,					lowerCAmelCase__ :     str			):
				__a           =			index  # the number when this node is seen
				__a           =			index  # lowest rank node reachable from here
				index += 1
				stack.append(lowerCAmelCase__			)
				__a           =			True

				for w in g[v]:
						if index_of[w] == -1:
								__a           =			strong_connect(lowerCAmelCase__    ,					lowerCAmelCase__    ,					lowerCAmelCase__			)
								__a           =			(
								    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
								)
						elif on_stack[w]:
								__a           =			(
								    lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
								)

				if lowlink_of[v] == index_of[v]:
						__a           =			[]
						__a           =			stack.pop()
						__a           =			False
						component.append(lowerCAmelCase__			)
						while w != v:
								__a           =			stack.pop()
								__a           =			False
								component.append(lowerCAmelCase__			)
						components.append(lowerCAmelCase__			)
				return index

		__a           =			[]
		for v in range(lowerCAmelCase__			):
				if index_of[v] == -1:
						strong_connect(lowerCAmelCase__    ,					0    ,					lowerCAmelCase__			)

		return components

def        lowercase							(		lowerCAmelCase__ :     str    ,					lowerCAmelCase__ :     Union[str, Any]			) ->      Optional[int]:
		__a           =			[[] for _ in range(lowerCAmelCase__			)]
		for u, v in edges:
				g[u].append(lowerCAmelCase__			)
		return g


if __name__ == "__main__":
				# Test
				lowercase_			     =  7
				lowercase_			     =  [0, 0, 1, 2, 3, 3, 4, 4, 6]
				lowercase_			     =  [1, 3, 2, 0, 1, 4, 5, 6, 5]
				lowercase_			     =  [(u, v) for u, v in zip(source, target)]
				lowercase_			     =  create_graph(n_vertices, edges)

				assert [[5], [6], [4], [3, 2, 1, 0]] == tarjan(g)










import math






def 							__lowercase   ( __lowerCAmelCase							:				int   ):
							a__             =     [True] * n
							a__             =     False
							a__             =     False
							a__             =     True

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

							a__             =     [2]

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

							return primes






def 							__lowercase   ( __lowerCAmelCase							:				int = 9_9_9_9_6_6_6_6_3_3_3_3   ):
							a__             =     math.floor(math.sqrt(__lowerCAmelCase   )   ) + 1_0_0
							a__             =     prime_sieve(__lowerCAmelCase   )

							a__             =     0
							a__             =     0
							a__             =     primes[prime_index]

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

														a__             =     last_prime**2
														a__             =     next_prime**2

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

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

							return matches_sum


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




