




'''simple docstring'''



from collections import deque




def   lowercase__(			__UpperCamelCase:					List[Any]    ):

      """simple docstring"""






      SCREAMING_SNAKE_CASE   :      Tuple    					=						len(__UpperCamelCase    )
      SCREAMING_SNAKE_CASE   :      str    					=						deque()
      SCREAMING_SNAKE_CASE   :      int    					=						[False for _ in range(__UpperCamelCase    )]
      SCREAMING_SNAKE_CASE   :      List[str]    					=						[-1 for _ in range(__UpperCamelCase    )]
      SCREAMING_SNAKE_CASE   :      str    					=						index_of[:]

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

            for w in g[v]:
                  if index_of[w] == -1:
                        SCREAMING_SNAKE_CASE   :      Tuple    					=						strong_connect(__UpperCamelCase      ,__UpperCamelCase      ,__UpperCamelCase    )
                        SCREAMING_SNAKE_CASE   :      int    					=						(
                            lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
                        )
                  elif on_stack[w]:
                        SCREAMING_SNAKE_CASE   :      str    					=						(
                            lowlink_of[w] if lowlink_of[w] < lowlink_of[v] else lowlink_of[v]
                        )

            if lowlink_of[v] == index_of[v]:
                  SCREAMING_SNAKE_CASE   :      Dict    					=						[]
                  SCREAMING_SNAKE_CASE   :      Dict    					=						stack.pop()
                  SCREAMING_SNAKE_CASE   :      Optional[int]    					=						False
                  component.append(__UpperCamelCase    )
                  while w != v:
                        SCREAMING_SNAKE_CASE   :      List[Any]    					=						stack.pop()
                        SCREAMING_SNAKE_CASE   :      int    					=						False
                        component.append(__UpperCamelCase    )
                  components.append(__UpperCamelCase    )
            return index

      SCREAMING_SNAKE_CASE   :      int    					=						[]
      for v in range(__UpperCamelCase    ):
            if index_of[v] == -1:
                  strong_connect(__UpperCamelCase      ,0      ,__UpperCamelCase    )

      return components




def   lowercase__(			__UpperCamelCase:					List[str]      ,__UpperCamelCase:					str    ):

      """simple docstring"""






      SCREAMING_SNAKE_CASE   :      Optional[Any]    					=						[[] for _ in range(__UpperCamelCase    )]
      for u, v in edges:
            g[u].append(__UpperCamelCase    )
      return g


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

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








'''simple docstring'''



def   lowercase__(			__UpperCamelCase:					int = 1_00_00_00    ):

      """simple docstring"""






      SCREAMING_SNAKE_CASE   :      Tuple    					=						[i - 1 for i in range(limit + 1    )]

      for i in range(2      ,limit + 1    ):
            if phi[i] == i - 1:
                  for j in range(2 * i      ,limit + 1      ,__UpperCamelCase    ):
                        phi[j] -= phi[j] // i

      return sum(phi[2 : limit + 1]    )


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


