




'''simple docstring'''





from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

_SCREAMING_SNAKE_CASE							:   Union[str, Any]      		= TypeVar("T")


def      UpperCamelCase_(	snake_case							:       Tuple     ):

							'''simple docstring'''






							return (position - 1) // 2


def      UpperCamelCase_(	snake_case							:       List[str]     ):

							'''simple docstring'''






							return (2 * position) + 1


def      UpperCamelCase_(	snake_case							:       Any     ):

							'''simple docstring'''






							return (2 * position) + 2




class  _snake_case		(	Generic[T]							):




			def __init__(					self							)				->				None:

										'''simple docstring'''




										snake_case_						=      []
										snake_case_						=      {}
										snake_case_						=      0




			def __len__(					self							)				->				int:

										'''simple docstring'''




										return self.elements




			def __repr__(					self							)				->				str:

										'''simple docstring'''




										return str(self.heap							)




			def    lowerCAmelCase__				(					self							)				->				bool:

										'''simple docstring'''




										return self.elements == 0




			def    lowerCAmelCase__				(					self				,							a__				,							a__							)				->				None:

										'''simple docstring'''




										self.heap.append((elem, weight)							)
										snake_case_						=      self.elements
										self.elements += 1
										self._bubble_up(a__							)




			def    lowerCAmelCase__				(					self							)				->				T:

										'''simple docstring'''




										if self.elements > 1:
																	self._swap_nodes(0				,							self.elements - 1							)
										snake_case_					,      snake_case_						=      self.heap.pop()
										del self.position_map[elem]
										self.elements -= 1
										if self.elements > 0:
																	snake_case_					,      snake_case_						=      self.heap[0]
																	self._bubble_down(a__							)
										return elem




			def    lowerCAmelCase__				(					self				,							a__				,							a__							)				->				None:

										'''simple docstring'''




										snake_case_						=      self.position_map[elem]
										snake_case_						=      (elem, weight)
										if position > 0:
																	snake_case_						=      get_parent_position(a__							)
																	snake_case_					,      snake_case_						=      self.heap[parent_position]
																	if parent_weight > weight:
																								self._bubble_up(a__							)
																	else:
																								self._bubble_down(a__							)
										else:
																	self._bubble_down(a__							)




			def    lowerCAmelCase__				(					self				,							a__							)				->				None:

										'''simple docstring'''




										snake_case_						=      self.position_map[elem]
										if curr_pos == 0:
																	return None
										snake_case_						=      get_parent_position(a__							)
										snake_case_					,      snake_case_						=      self.heap[curr_pos]
										snake_case_					,      snake_case_						=      self.heap[parent_position]
										if parent_weight > weight:
																	self._swap_nodes(a__				,							a__							)
																	return self._bubble_up(a__							)
										return None




			def    lowerCAmelCase__				(					self				,							a__							)				->				None:

										'''simple docstring'''




										snake_case_						=      self.position_map[elem]
										snake_case_					,      snake_case_						=      self.heap[curr_pos]
										snake_case_						=      get_child_left_position(a__							)
										snake_case_						=      get_child_right_position(a__							)
										if child_left_position < self.elements and child_right_position < self.elements:
																	snake_case_					,      snake_case_						=      self.heap[child_left_position]
																	snake_case_					,      snake_case_						=      self.heap[child_right_position]
																	if child_right_weight < child_left_weight and child_right_weight < weight:
																								self._swap_nodes(a__				,							a__							)
																								return self._bubble_down(a__							)
										if child_left_position < self.elements:
																	snake_case_					,      snake_case_						=      self.heap[child_left_position]
																	if child_left_weight < weight:
																								self._swap_nodes(a__				,							a__							)
																								return self._bubble_down(a__							)
										else:
																	return None
										if child_right_position < self.elements:
																	snake_case_					,      snake_case_						=      self.heap[child_right_position]
																	if child_right_weight < weight:
																								self._swap_nodes(a__				,							a__							)
																								return self._bubble_down(a__							)
										return None




			def    lowerCAmelCase__				(					self				,							a__				,							a__							)				->				None:

										'''simple docstring'''




										snake_case_						=      self.heap[nodea_pos][0]
										snake_case_						=      self.heap[nodea_pos][0]
										snake_case_					,      snake_case_						=      (
										    self.heap[nodea_pos],
										    self.heap[nodea_pos],
										)
										snake_case_						=      nodea_pos
										snake_case_						=      nodea_pos




class  _snake_case		(	Generic[T]							):




			def __init__(					self							)				->				None:

										'''simple docstring'''




										snake_case_						=      {}
										snake_case_						=      0




			def __repr__(					self							)				->				str:

										'''simple docstring'''




										return str(self.connections							)




			def __len__(					self							)				->				int:

										'''simple docstring'''




										return self.nodes




			def    lowerCAmelCase__				(					self				,							a__							)				->				None:

										'''simple docstring'''




										if node not in self.connections:
																	snake_case_						=      {}
																	self.nodes += 1




			def    lowerCAmelCase__				(					self				,							a__				,							a__				,							a__							)				->				None:

										'''simple docstring'''




										self.add_node(a__							)
										self.add_node(a__							)
										snake_case_						=      weight
										snake_case_						=      weight


def      UpperCamelCase_(	snake_case							:       Union[str, Any]							,				):

							'''simple docstring'''






							snake_case_						=      {node: maxsize for node in graph.connections}
							snake_case_						=      {node: None for node in graph.connections}

							snake_case_						=      MinPriorityQueue()
							for node, weight in dist.items():
														priority_queue.push(__A							,				__A     )

							if priority_queue.is_empty():
														return dist, parent

							# initialization
							snake_case_						=      priority_queue.extract_min()
							snake_case_						=      0
							for neighbour in graph.connections[node]:
														if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
																					snake_case_						=      dist[node] + graph.connections[node][neighbour]
																					priority_queue.update_key(__A							,				dist[neighbour]     )
																					snake_case_						=      node

    # running prim's algorithm
							while not priority_queue.is_empty():
														snake_case_						=      priority_queue.extract_min()
														for neighbour in graph.connections[node]:
																					if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
																												snake_case_						=      dist[node] + graph.connections[node][neighbour]
																												priority_queue.update_key(__A							,				dist[neighbour]     )
																												snake_case_						=      node
							return dist, parent









'''simple docstring'''





from math import sqrt




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (
         number >= 0
     ), "'number' must been an int and positive"

     _a      =  True

     # 0 and 1 are none primes.
     if number <= 1:
          _a      =  False

     for divisor in range(2  ,	int(round(sqrt(__A))) + 1):
          # if 'number' divisible by 'divisor' then sets 'status'
          # of false and break up the loop.
          if number % divisor == 0:
               _a      =  False
               break

    # precondition
     assert isinstance(__A  ,	__A), "'status' must been from type bool"

     return status




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (n > 2), "'N' must been an int and > 2"

     # beginList: contains all natural numbers from 2 up to N
     _a      =  list(range(2  ,	n + 1))

     _a      =  []  # this list will be returns.

     # actual sieve of erathostenes
     for i in range(len(__A)):
          for j in range(i + 1  ,	len(__A)):
               if (begin_list[i] != 0) and (begin_list[j] % begin_list[i] == 0):
                    _a      =  0

    # filters actual prime numbers.
     _a      =  [x for x in begin_list if x != 0]

     # precondition
     assert isinstance(__A  ,	__A), "'ans' must been from type list"

     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (n > 2), "'N' must been an int and > 2"

     _a      =  []

     # iterates over all numbers between 2 up to N+1
     # if a number is prime then appends to list 'ans'
     for number in range(2  ,	n + 1):
          if is_prime(__A):
               ans.append(__A)

    # precondition
     assert isinstance(__A  ,	__A), "'ans' must been from type list"

     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and number >= 0, "'number' must been an int and >= 0"

     _a      =  []  # this list will be returns of the function.

     # potential prime number factors.

     _a      =  2

     _a      =  number

     if number == 0 or number == 1:
          ans.append(__A)

     # if 'number' not prime then builds the prime factorization of 'number'
     elif not is_prime(__A):
          while quotient != 1:
               if is_prime(__A) and (quotient % factor == 0):
                    ans.append(__A)
                    quotient /= factor
               else:
                    factor += 1

     else:
          ans.append(__A)

     # precondition
     assert isinstance(__A  ,	__A), "'ans' must been from type list"

     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (
         number >= 0
     ), "'number' bust been an int and >= 0"

     _a      =  0

     # prime factorization of 'number'
     _a      =  prime_factorization(__A)

     _a      =  max(__A)

     # precondition
     assert isinstance(__A  ,	__A), "'ans' must been from type int"

     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (
         number >= 0
     ), "'number' bust been an int and >= 0"

     _a      =  0

     # prime factorization of 'number'
     _a      =  prime_factorization(__A)

     _a      =  min(__A)

     # precondition
     assert isinstance(__A  ,	__A), "'ans' must been from type int"

     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A), "'number' must been an int"
     assert isinstance(number % 2 == 0  ,	__A), "compare bust been from type bool"

     return number % 2 == 0




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A), "'number' must been an int"
     assert isinstance(number % 2 != 0  ,	__A), "compare bust been from type bool"

     return number % 2 != 0




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert (
         isinstance(__A  ,	__A) and (number > 2) and is_even(__A)
     ), "'number' must been an int, even and > 2"

     _a      =  []  # this list will returned

     # creates a list of prime numbers between 2 up to 'number'
     _a      =  get_prime_numbers(__A)
     _a      =  len(__A)

     # run variable for while-loops.
     _a      =  0
     _a      =  None

     # exit variable. for break up the loops
     _a      =  True

     while i < len_pn and loop:
          _a      =  i + 1

          while j < len_pn and loop:
               if prime_numbers[i] + prime_numbers[j] == number:
                    _a      =  False
                    ans.append(prime_numbers[i])
                    ans.append(prime_numbers[j])

               j += 1

          i += 1

     # precondition
     assert (
         isinstance(__A  ,	__A)
         and (len(__A) == 2)
         and (ans[0] + ans[1] == number)
         and is_prime(ans[0])
         and is_prime(ans[1])
     ), "'ans' must contains two primes. And sum of elements must been eq 'number'"

     return ans




def lowerCAmelCase  (__A  ,	__A):



     """simple docstring"""



     assert (
         isinstance(__A  ,	__A)
         and isinstance(__A  ,	__A)
         and (numbera >= 0)
         and (numbera >= 0)
     ), "'number1' and 'number2' must been positive integer."

     _a      =  0

     while numbera != 0:
          _a      =  numbera % numbera
          _a      =  numbera
          _a      =  rest

     # precondition
     assert isinstance(__A  ,	__A) and (
         numbera >= 0
     ), "'number' must been from type int and positive"

     return numbera




def lowerCAmelCase  (__A  ,	__A):



     """simple docstring"""



     assert (
         isinstance(__A  ,	__A)
         and isinstance(__A  ,	__A)
         and (numbera >= 1)
         and (numbera >= 1)
     ), "'number1' and 'number2' must been positive integer."

     _a      =  1  # actual answer that will be return.

     # for kgV (x,1)
     if numbera > 1 and numbera > 1:
          # builds the prime factorization of 'number1' and 'number2'
          _a      =  prime_factorization(__A)
          _a      =  prime_factorization(__A)

     elif numbera == 1 or numbera == 1:
          _a      =  []
          _a      =  []
          _a      =  max(__A  ,	__A)

     _a      =  0
     _a      =  0

     _a      =  []  # captured numbers int both 'primeFac1' and 'primeFac2'

     # iterates through primeFac1
     for n in prime_fac_a:
          if n not in done:
               if n in prime_fac_a:
                    _a      =  prime_fac_a.count(__A)
                    _a      =  prime_fac_a.count(__A)

                    for _ in range(max(__A  ,	__A)):
                         ans *= n

               else:
                    _a      =  prime_fac_a.count(__A)

                    for _ in range(__A):
                         ans *= n

               done.append(__A)

    # iterates through primeFac2
     for n in prime_fac_a:
          if n not in done:
               _a      =  prime_fac_a.count(__A)

               for _ in range(__A):
                    ans *= n

               done.append(__A)

    # precondition
     assert isinstance(__A  ,	__A) and (
         ans >= 0
     ), "'ans' must been from type int and positive"

     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (n >= 0), "'number' must been a positive int"

     _a      =  0
     _a      =  2  # this variable holds the answer

     while index < n:
          index += 1

          ans += 1  # counts to the next number

          # if ans not prime then
          # runs to the next prime number.
          while not is_prime(__A):
               ans += 1

    # precondition
     assert isinstance(__A  ,	__A) and is_prime(
         __A), "'ans' must been a prime number and from type int"

     return ans




def lowerCAmelCase  (__A  ,	__A):



     """simple docstring"""



     assert (
         is_prime(__A) and is_prime(__A) and (p_number_a < p_number_a)
     ), "The arguments must been prime numbers and 'pNumber1' < 'pNumber2'"

     _a      =  p_number_a + 1  # jump to the next number

     _a      =  []  # this list will be returns.

     # if number is not prime then
     # fetch the next prime number.
     while not is_prime(__A):
          number += 1

     while number < p_number_a:
          ans.append(__A)

          number += 1

          # fetch the next prime number.
          while not is_prime(__A):
               number += 1

    # precondition
     assert (
         isinstance(__A  ,	__A)
         and ans[0] != p_number_a
         and ans[len(__A) - 1] != p_number_a
     ), "'ans' must been a list without the arguments"

     # 'ans' contains not 'pNumber1' and 'pNumber2' !
     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (n >= 1), "'n' must been int and >= 1"

     _a      =  []  # will be returned.

     for divisor in range(1  ,	n + 1):
          if n % divisor == 0:
               ans.append(__A)

    # precondition
     assert ans[0] == 1 and ans[len(__A) - 1] == n, "Error in function getDivisiors(...)"

     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (
         number > 1
     ), "'number' must been an int and >= 1"

     _a      =  get_divisors(__A)

     # precondition
     assert (
         isinstance(__A  ,	__A)
         and (divisors[0] == 1)
         and (divisors[len(__A) - 1] == number)
     ), "Error in help-function getDivisiors(...)"

     # summed all divisors up to 'number' (exclusive), hence [:-1]
     return sum(divisors[:-1]) == number




def lowerCAmelCase  (__A  ,	__A):



     """simple docstring"""



     assert (
         isinstance(__A  ,	__A)
         and isinstance(__A  ,	__A)
         and (denominator != 0)
     ), "The arguments must been from type int and 'denominator' != 0"

     # build the greatest common divisor of numerator and denominator.
     _a      =  gcd(abs(__A)  ,	abs(__A))

     # precondition
     assert (
         isinstance(__A  ,	__A)
         and (numerator % gcd_of_fraction == 0)
         and (denominator % gcd_of_fraction == 0)
     ), "Error in function gcd(...,...)"

     return (numerator // gcd_of_fraction, denominator // gcd_of_fraction)




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (n >= 0), "'n' must been a int and >= 0"

     _a      =  1  # this will be return.

     for factor in range(1  ,	n + 1):
          ans *= factor

     return ans




def lowerCAmelCase  (__A):



     """simple docstring"""



     assert isinstance(__A  ,	__A) and (n >= 0), "'n' must been an int and >= 0"

     _a      =  0
     _a      =  1
     _a      =  1  # this will be return

     for _ in range(n - 1):
          _a      =  ans
          ans += fiba
          _a      =  tmp

     return ans



