




'''simple docstring'''



import math
import sys







class 	lowercase_					:


   """simple docstring"""

   def __init__(					self      :			List[str]					):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE =   0
      _SCREAMING_SNAKE_CASE =   []
      _SCREAMING_SNAKE_CASE =   {}  # To store the pos of node in array



   def 							lowerCAmelCase_    (					self      :			Optional[Any]					):

      """simple docstring"""
      return self.cur_size == 0



   def 							lowerCAmelCase_    (					self      :			Union[str, Any]						,   __lowerCamelCase      :			List[Any]					):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE =   self.left(__lowerCamelCase					)
      _SCREAMING_SNAKE_CASE =   self.right(__lowerCamelCase					)
      if lc < self.cur_size and self.array(__lowerCamelCase					)[0] < self.array(__lowerCamelCase					)[0]:
         _SCREAMING_SNAKE_CASE =   lc
      else:
         _SCREAMING_SNAKE_CASE =   idx
      if rc < self.cur_size and self.array(__lowerCamelCase					)[0] < self.array(__lowerCamelCase					)[0]:
         _SCREAMING_SNAKE_CASE =   rc
      if smallest != idx:
         self.swap(__lowerCamelCase						,   __lowerCamelCase					)
         self.min_heapify(__lowerCamelCase					)



   def 							lowerCAmelCase_    (					self      :			Union[str, Any]						,   __lowerCamelCase      :			str					):

      """simple docstring"""
      # Inserts a node into the Priority Queue
      _SCREAMING_SNAKE_CASE =   self.cur_size
      self.cur_size += 1
      self.array.append((sys.maxsize, tup[1])					)
      self.decrease_key((sys.maxsize, tup[1])						,   tup[0]					)



   def 							lowerCAmelCase_    (					self      :			List[Any]					):

      """simple docstring"""
      # Removes and returns the min element at top of priority queue
      _SCREAMING_SNAKE_CASE =   self.array[0][1]
      _SCREAMING_SNAKE_CASE =   self.array[self.cur_size - 1]
      self.cur_size -= 1
      self.min_heapify(1					)
      del self.pos[min_node]
      return min_node



   def 							lowerCAmelCase_    (					self      :			Any						,   __lowerCamelCase      :			str					):

      """simple docstring"""
      # returns the index of left child
      return 2 * i + 1



   def 							lowerCAmelCase_    (					self      :			List[str]						,   __lowerCamelCase      :			int					):

      """simple docstring"""
      # returns the index of right child
      return 2 * i + 2



   def 							lowerCAmelCase_    (					self      :			Optional[int]						,   __lowerCamelCase      :			str					):

      """simple docstring"""
      # returns the index of parent
      return math.floor(i / 2					)



   def 							lowerCAmelCase_    (					self      :			Tuple						,   __lowerCamelCase      :			Any						,   __lowerCamelCase      :			Optional[Any]					):

      """simple docstring"""
      # swaps array elements at indices i and j
      # update the pos{}
      _SCREAMING_SNAKE_CASE =   j
      _SCREAMING_SNAKE_CASE =   i
      _SCREAMING_SNAKE_CASE =   self.array[i]
      _SCREAMING_SNAKE_CASE =   self.array[j]
      _SCREAMING_SNAKE_CASE =   temp



   def 							lowerCAmelCase_    (					self      :			Optional[int]						,   __lowerCamelCase      :			Optional[Any]						,   __lowerCamelCase      :			Optional[Any]					):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE =   self.pos[tup[1]]
      # assuming the new_d is atmost old_d
      _SCREAMING_SNAKE_CASE =   (new_d, tup[1])
      while idx > 0 and self.array[self.par(__lowerCamelCase					)][0] > self.array[idx][0]:
         self.swap(__lowerCamelCase						,   self.par(__lowerCamelCase					)					)
         _SCREAMING_SNAKE_CASE =   self.par(__lowerCamelCase					)







class 	lowercase_					:


   """simple docstring"""

   def __init__(					self      :			Any						,   __lowerCamelCase      :			Optional[int]					):

      """simple docstring"""
      _SCREAMING_SNAKE_CASE =   {}  # To store graph: u -> (v,w)
      _SCREAMING_SNAKE_CASE =   num  # Number of nodes in graph
      # To store the distance from source vertex
      _SCREAMING_SNAKE_CASE =   [0] * self.num_nodes
      _SCREAMING_SNAKE_CASE =   [-1] * self.num_nodes  # To store the path



   def 							lowerCAmelCase_    (					self      :			Optional[int]						,   __lowerCamelCase      :			List[Any]						,   __lowerCamelCase      :			int						,   __lowerCamelCase      :			Dict					):

      """simple docstring"""
      #  Edge going from node u to v and v to u with weight w
      # u (w)-> v, v (w) -> u
      # Check if u already in graph
      if u in self.adjList:
         self.adjList[u].append((v, w)					)
      else:
         _SCREAMING_SNAKE_CASE =   [(v, w)]

      # Assuming undirected graph
      if v in self.adjList:
         self.adjList[v].append((u, w)					)
      else:
         _SCREAMING_SNAKE_CASE =   [(u, w)]



   def 							lowerCAmelCase_    (					self      :			List[str]					):

      """simple docstring"""
      # u -> v(w)
      for u in self.adjList:
         print(__lowerCamelCase						,   "->"						,   " -> ".join(str(F"""{v}({w})"""					) for v, w in self.adjList[u]					)					)



   def 							lowerCAmelCase_    (					self      :			List[str]						,   __lowerCamelCase      :			int					):

      """simple docstring"""
      # Flush old junk values in par[]
      _SCREAMING_SNAKE_CASE =   [-1] * self.num_nodes
      # src is the source node
      _SCREAMING_SNAKE_CASE =   0
      _SCREAMING_SNAKE_CASE =   PriorityQueue()
      q.insert((0, src)					)  # (dist from src, node)
      for u in self.adjList:
         if u != src:
            _SCREAMING_SNAKE_CASE =   sys.maxsize  # Infinity
            _SCREAMING_SNAKE_CASE =   -1

      while not q.is_empty():
         _SCREAMING_SNAKE_CASE =   q.extract_min()  # Returns node with the min dist from source
         # Update the distance of all the neighbours of u and
         # if their prev dist was INFINITY then push them in Q
         for v, w in self.adjList[u]:
            _SCREAMING_SNAKE_CASE =   self.dist[u] + w
            if self.dist[v] > new_dist:
               if self.dist[v] == sys.maxsize:
                  q.insert((new_dist, v)					)
               else:
                  q.decrease_key((self.dist[v], v)						,   __lowerCamelCase					)
               _SCREAMING_SNAKE_CASE =   new_dist
               _SCREAMING_SNAKE_CASE =   u

        # Show the shortest distances from src
      self.show_distances(__lowerCamelCase					)



   def 							lowerCAmelCase_    (					self      :			Any						,   __lowerCamelCase      :			Any					):

      """simple docstring"""
      print(F"""Distance from node: {src}"""					)
      for u in range(self.num_nodes					):
         print(F"""Node {u} has distance: {self.dist[u]}"""					)



   def 							lowerCAmelCase_    (					self      :			Union[str, Any]						,   __lowerCamelCase      :			List[Any]						,   __lowerCamelCase      :			Optional[Any]					):

      """simple docstring"""
      # To show the shortest path from src to dest
      # WARNING: Use it *after* calling dijkstra
      _SCREAMING_SNAKE_CASE =   []
      _SCREAMING_SNAKE_CASE =   0
      _SCREAMING_SNAKE_CASE =   dest
      # Backtracking from dest to src
      while self.par[temp] != -1:
         path.append(__lowerCamelCase					)
         if temp != src:
            for v, w in self.adjList[temp]:
               if v == self.par[temp]:
                  cost += w
                  break
         _SCREAMING_SNAKE_CASE =   self.par[temp]
      path.append(__lowerCamelCase					)
      path.reverse()

      print(F"""----Path to reach {dest} from {src}----"""					)
      for u in path:
         print(F"""{u}"""						,   end=" "					)
         if u != dest:
            print("-> "						,   end=""					)

      print("\nTotal cost of path: "						,   __lowerCamelCase					)


if __name__ == "__main__":
 lowerCamelCase_	 =		Graph(9)
 graph.add_edge(0, 1, 4)
 graph.add_edge(0, 7, 8)
 graph.add_edge(1, 2, 8)
 graph.add_edge(1, 7, 11)
 graph.add_edge(2, 3, 7)
 graph.add_edge(2, 8, 2)
 graph.add_edge(2, 5, 4)
 graph.add_edge(3, 4, 9)
 graph.add_edge(3, 5, 14)
 graph.add_edge(4, 5, 10)
 graph.add_edge(5, 6, 2)
 graph.add_edge(6, 7, 1)
 graph.add_edge(6, 8, 6)
 graph.add_edge(7, 8, 7)
 graph.show_graph()
 graph.dijkstra(0)
 graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21







'''simple docstring'''



import math
def 				SCREAMING_SNAKE_CASE_				(							__A       :				Tuple						)				->				List[Any]:
   _SCREAMING_SNAKE_CASE =   0
   if n % 2 == 0:
      count += 1
      while n % 2 == 0:
         _SCREAMING_SNAKE_CASE =   int(n / 2						)
    # the n input value must be odd so that
    # we can skip one element (ie i += 2)

   _SCREAMING_SNAKE_CASE =   3

   while i <= int(math.sqrt(__A						)						):
      if n % i == 0:
         count += 1
         while n % i == 0:
            _SCREAMING_SNAKE_CASE =   int(n / i						)
      _SCREAMING_SNAKE_CASE =   i + 2

   # this condition checks the prime
   # number n is greater than 2

   if n > 2:
      count += 1
   return count


if __name__ == "__main__":
 lowerCamelCase_	 =		51_24_21_83
 print(f'''The number of distinct prime factors is/are {exact_prime_factor_count(n)}''')
 print(f'''The value of log(log(n)) is {math.log(math.log(n)):.4f}''')

