


from __future__ import annotations

from collections.abc import MutableSequence



class        a					:





     def __init__(    self					:				Optional[int]    ,	SCREAMING_SNAKE_CASE_					:				Tuple    ,	SCREAMING_SNAKE_CASE_					:				Optional[int]							):
        if len(SCREAMING_SNAKE_CASE_							) != degree + 1:
           raise ValueError(
               """The number of coefficients should be equal to the degree + 1."""							)

        __lowerCamelCase:				Tuple     =	list(SCREAMING_SNAKE_CASE_							)
        __lowerCamelCase:				Tuple     =	degree





     def __add__(    self					:				Tuple    ,	SCREAMING_SNAKE_CASE_					:				int							):

        if self.degree > polynomial_a.degree:
           __lowerCamelCase:				int     =	self.coefficients[:]
           for i in range(polynomial_a.degree + 1							):
              coefficients[i] += polynomial_a.coefficients[i]
           return Polynomial(self.degree    ,	SCREAMING_SNAKE_CASE_							)
        else:
           __lowerCamelCase:				List[str]     =	polynomial_a.coefficients[:]
           for i in range(self.degree + 1							):
              coefficients[i] += self.coefficients[i]
           return Polynomial(polynomial_a.degree    ,	SCREAMING_SNAKE_CASE_							)





     def __sub__(    self					:				List[Any]    ,	SCREAMING_SNAKE_CASE_					:				Optional[int]							):
        return self + polynomial_a * Polynomial(0    ,	[-1]							)





     def __neg__(    self					:				Dict							):
        return Polynomial(self.degree    ,	[-c for c in self.coefficients]							)





     def __mul__(    self					:				Dict    ,	SCREAMING_SNAKE_CASE_					:				List[Any]							):
        __lowerCamelCase:				Dict     =	[0] * (self.degree + polynomial_a.degree + 1)
        for i in range(self.degree + 1							):
           for j in range(polynomial_a.degree + 1							):
              coefficients[i + j] += (
                  self.coefficients[i] * polynomial_a.coefficients[j]
              )

        return Polynomial(self.degree + polynomial_a.degree    ,	SCREAMING_SNAKE_CASE_							)





     def  a_       (    self					:				Optional[int]    ,	SCREAMING_SNAKE_CASE_					:				Any							):
        __lowerCamelCase:				Any     =	0
        for i in range(self.degree + 1							):
           result += self.coefficients[i] * (substitution**i)
        return result





     def __str__(    self					:				Optional[Any]							):
        __lowerCamelCase:				Tuple     =	""""""
        for i in range(self.degree    ,	-1    ,	-1							):
           if self.coefficients[i] == 0:
              continue
           elif self.coefficients[i] > 0:
              if polynomial:
                 polynomial += " + "
           else:
              polynomial += " - "

           if i == 0:
              polynomial += str(abs(self.coefficients[i]							)							)
           elif i == 1:
              polynomial += str(abs(self.coefficients[i]							)							) + "x"
           else:
              polynomial += str(abs(self.coefficients[i]							)							) + "x^" + str(SCREAMING_SNAKE_CASE_							)

        return polynomial





     def __repr__(    self					:				Optional[int]							):
        return self.__str__()





     def  a_       (    self					:				Union[str, Any]							):
        __lowerCamelCase:				int     =	[0] * self.degree
        for i in range(self.degree							):
           __lowerCamelCase:				Optional[Any]     =	self.coefficients[i + 1] * (i + 1)
        return Polynomial(self.degree - 1    ,	SCREAMING_SNAKE_CASE_							)





     def  a_       (    self					:				Optional[Any]    ,	SCREAMING_SNAKE_CASE_					:				Optional[Any] = 0							):
        __lowerCamelCase:				Optional[Any]     =	[0] * (self.degree + 2)
        __lowerCamelCase:				Dict     =	constant
        for i in range(self.degree + 1							):
           __lowerCamelCase:				int     =	self.coefficients[i] / (i + 1)
        return Polynomial(self.degree + 1    ,	SCREAMING_SNAKE_CASE_							)





     def __eq__(    self					:				List[Any]    ,	SCREAMING_SNAKE_CASE_					:				int							):
        if not isinstance(SCREAMING_SNAKE_CASE_    ,	SCREAMING_SNAKE_CASE_							):
           return False

        if self.degree != polynomial_a.degree:
           return False

        for i in range(self.degree + 1							):
           if self.coefficients[i] != polynomial_a.coefficients[i]:
              return False

        return True







     def __ne__(    self					:				List[str]    ,	SCREAMING_SNAKE_CASE_					:				List[Any]							):
        return not self.__eq__(SCREAMING_SNAKE_CASE_							)






def     __lowerCAmelCase						(							snake_case	:    int = 1000000 )       ->							int:
   __lowerCamelCase:				Union[str, Any]     =	set(range(3						,      snake_case						,      2 ) )
   primes.add(2 )
   for p in range(3						,      snake_case						,      2 ):
      if p not in primes:
         continue
      primes.difference_update(set(range(p * p						,      snake_case						,      snake_case ) ) )

   __lowerCamelCase:				Any     =	[float(snake_case ) for n in range(limit + 1 )]

   for p in primes:
      for n in range(snake_case						,      limit + 1						,      snake_case ):
         phi[n] *= 1 - 1 / p

   return int(sum(phi[2:] ) )


if __name__ == "__main__":
   print(F"""{solution() = }""")


