






snake_case			 =						float("""inf""")


class        SCREAMING_SNAKE_CASE	:
     '''simple docstring'''


     def __init__( self				:		Optional[int]    ,       UpperCAmelCase_				:		str					):
       SCREAMING_SNAKE_CASE				:					Any		  =			[0] * n
       SCREAMING_SNAKE_CASE				:					Dict		  =			[0] * n
       SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			[0] * n
       SCREAMING_SNAKE_CASE				:					Optional[Any]		  =			[[] for _ in range(UpperCAmelCase_					)]


     def  _A				( self				:		Optional[Any]    ,       UpperCAmelCase_				:		Tuple    ,       UpperCAmelCase_				:		int    ,       UpperCAmelCase_				:		Optional[int]    ,       UpperCAmelCase_				:		Dict=0					):
       self.adj[a].append([b, len(self.adj[b]					), c, 0]					)
       self.adj[b].append([a, len(self.adj[a]					) - 1, rcap, 0]					)


     def  _A				( self				:		Any    ,       UpperCAmelCase_				:		Union[str, Any]    ,       UpperCAmelCase_				:		Tuple    ,       UpperCAmelCase_				:		List[str]					):
       if vertex == sink or not flow:
         return flow

       for i in range(self.ptr[vertex]    ,       len(self.adj[vertex]					)					):
         SCREAMING_SNAKE_CASE				:					Tuple		  =			self.adj[vertex][i]
         if self.lvl[e[0]] == self.lvl[vertex] + 1:
           SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			self.depth_first_search(e[0]    ,       UpperCAmelCase_    ,       min(UpperCAmelCase_    ,       e[2] - e[3]					)					)
           if p:
             self.adj[vertex][i][3] += p
             self.adj[e[0]][e[1]][3] -= p
             return p
         SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			self.ptr[vertex] + 1
       return 0






     def  _A				( self				:		Union[str, Any]    ,       UpperCAmelCase_				:		Dict    ,       UpperCAmelCase_				:		Union[str, Any]					):
       SCREAMING_SNAKE_CASE  ,     SCREAMING_SNAKE_CASE				:					List[Any]		  =			0, source
       for l in range(31					):  # noqa: E741  l = 30 maybe faster for random data
         while True:
           SCREAMING_SNAKE_CASE  ,     SCREAMING_SNAKE_CASE				:					Tuple		  =			[0] * len(self.q					), [0] * len(self.q					)
           SCREAMING_SNAKE_CASE  ,     SCREAMING_SNAKE_CASE  ,     SCREAMING_SNAKE_CASE				:					Dict		  =			0, 1, 1
           while qi < qe and not self.lvl[sink]:
             SCREAMING_SNAKE_CASE				:					List[str]		  =			self.q[qi]
             qi += 1
             for e in self.adj[v]:
               if not self.lvl[e[0]] and (e[2] - e[3]) >> (30 - l):
                 SCREAMING_SNAKE_CASE				:					Union[str, Any]		  =			e[0]
                 qe += 1
                 SCREAMING_SNAKE_CASE				:					Dict		  =			self.lvl[v] + 1

           SCREAMING_SNAKE_CASE				:					str		  =			self.depth_first_search(UpperCAmelCase_    ,       UpperCAmelCase_    ,       UpperCAmelCase_					)
           while p:
             flow += p
             SCREAMING_SNAKE_CASE				:					Any		  =			self.depth_first_search(UpperCAmelCase_    ,       UpperCAmelCase_    ,       UpperCAmelCase_					)

           if not self.lvl[sink]:
             break

       return flow
snake_case			 =						Dinic(10)
snake_case			 =						0
snake_case			 =						9
for vertex in range(1, 5):
   graph.add_edge(source, vertex, 1)
for vertex in range(5, 9):
   graph.add_edge(vertex, sink, 1)
for vertex in range(1, 5):
   graph.add_edge(vertex, vertex + 4, 1)

# Now we can know that is the maximum flow(source -> sink)
print(graph.max_flow(source, sink))














import math
from collections.abc import Generator


def      lowerCamelCase__	(   lowercase ):

  """simple docstring"""






  SCREAMING_SNAKE_CASE				:					Generator		  =			(i for i in range(1  ,   (max_n + 1) ))
  for i in (n for n in numbers if n > 1):
    for j in range(2  ,   lowercase ):
      if (i % j) == 0:
        break
    else:
      yield i


def      lowerCamelCase__	(   lowercase ):

  """simple docstring"""






  SCREAMING_SNAKE_CASE				:					Generator		  =			(i for i in range(1  ,   (max_n + 1) ))
  for i in (n for n in numbers if n > 1):
    # only need to check for factors up to sqrt(i)
    SCREAMING_SNAKE_CASE				:					str		  =			int(math.sqrt(lowercase ) ) + 1
    for j in range(2  ,   lowercase ):
      if (i % j) == 0:
        break
    else:
      yield i


def      lowerCamelCase__	(   lowercase ):

  """simple docstring"""






  SCREAMING_SNAKE_CASE				:					Generator		  =			(i for i in range(1  ,   (max_n + 1)  ,   2 ))
  # It's useless to test even numbers as they will not be prime
  if max_n > 2:
    yield 2  # Because 2 will not be tested, it's necessary to yield it now
  for i in (n for n in numbers if n > 1):
    SCREAMING_SNAKE_CASE				:					Optional[Any]		  =			int(math.sqrt(lowercase ) ) + 1
    for j in range(3  ,   lowercase  ,   2 ):
      # As we removed the even numbers, we don't need them now
      if (i % j) == 0:
        break
    else:
      yield i


def      lowerCamelCase__	(   ):

  """simple docstring"""






  from timeit import timeit

  SCREAMING_SNAKE_CASE				:					Tuple		  =			"from __main__ import slow_primes, primes, fast_primes"
  print(timeit("slow_primes(1_000_000_000_000)"  ,   setup=lowercase  ,   number=1000000 ) )
  print(timeit("primes(1_000_000_000_000)"  ,   setup=lowercase  ,   number=1000000 ) )
  print(timeit("fast_primes(1_000_000_000_000)"  ,   setup=lowercase  ,   number=1000000 ) )


if __name__ == "__main__":
   snake_case			 =						int(input("""Calculate primes up to:\n>> """).strip())
   for ret in primes(number):
      print(ret)
   benchmark()






