





"""simple docstring"""





class 			snake_case		:





      class 			snake_case		:
            lowerCamelCase__						= '''_prev''', '''_data''', '''_next'''

            def __init__(			self   :Dict						,							_lowerCamelCase   :Dict						,							_lowerCamelCase   :List[Any]						,							_lowerCamelCase   :Dict						):
             __SCREAMING_SNAKE_CASE :			Optional[Any]												=       link_p
             __SCREAMING_SNAKE_CASE :			int												=       element
             __SCREAMING_SNAKE_CASE :			Any												=       link_n



            def 						SCREAMING_SNAKE_CASE_			(			self   :str						):
             return (
                 f''' Prev -> {self._prev is not None}, Next -> {self._next is not None}'''
             )







      def __init__(			self   :Tuple						):
       __SCREAMING_SNAKE_CASE :			List[str]												=       self._Node(__UpperCAmelCase						,							__UpperCAmelCase						,							__UpperCAmelCase						)
       __SCREAMING_SNAKE_CASE :			Dict												=       self._Node(__UpperCAmelCase						,							__UpperCAmelCase						,							__UpperCAmelCase						)
       __SCREAMING_SNAKE_CASE :			Any												=       self._trailer
       __SCREAMING_SNAKE_CASE :			Any												=       self._header
       __SCREAMING_SNAKE_CASE :			int												=       0

      def __len__(			self   :List[Any]						):
       return self._size

      def 						SCREAMING_SNAKE_CASE_			(			self   :str						):
       return self.__len__() == 0

      def 						SCREAMING_SNAKE_CASE_			(			self   :Optional[int]						,							_lowerCamelCase   :Union[str, Any]						,							_lowerCamelCase   :Dict						,							_lowerCamelCase   :Tuple						):
       # Create new_node by setting it's prev.link -> header
       # setting it's next.link -> trailer
       __SCREAMING_SNAKE_CASE :			Any												=       self._Node(__UpperCAmelCase						,							__UpperCAmelCase						,							__UpperCAmelCase						)
       __SCREAMING_SNAKE_CASE :			Dict												=       new_node
       __SCREAMING_SNAKE_CASE :			Any												=       new_node
       self._size += 1
       return self



      def 						SCREAMING_SNAKE_CASE_			(			self   :Any						,							_lowerCamelCase   :Union[str, Any]						):
       __SCREAMING_SNAKE_CASE :			List[Any]												=       node._prev
       __SCREAMING_SNAKE_CASE :			int												=       node._next

       __SCREAMING_SNAKE_CASE :			Tuple												=       successor
       __SCREAMING_SNAKE_CASE :			int												=       predecessor
       self._size -= 1
       __SCREAMING_SNAKE_CASE :			List[Any]												=       node._data
       __SCREAMING_SNAKE_CASE :			Dict												=       None
       del node
       return temp







class 			snake_case		(   _DoublyLinkedBase   ):

      def 						SCREAMING_SNAKE_CASE_			(			self   :Tuple						):
       if self.is_empty():
        raise Exception('''List is empty'''						)
       return self._header._next._data

      def 						SCREAMING_SNAKE_CASE_			(			self   :Tuple						):
       if self.is_empty():
        raise Exception('''List is empty'''						)
       return self._trailer._prev._data

      def 						SCREAMING_SNAKE_CASE_			(			self   :Any						,							_lowerCamelCase   :int						):
       return self._insert(self._header						,							__UpperCAmelCase						,							self._header._next						)

      def 						SCREAMING_SNAKE_CASE_			(			self   :int						,							_lowerCamelCase   :List[Any]						):
       return self._insert(self._trailer._prev						,							__UpperCAmelCase						,							self._trailer						)

      def 						SCREAMING_SNAKE_CASE_			(			self   :Union[str, Any]						):
       if self.is_empty():
        raise IndexError('''remove_first from empty list'''						)
       return self._delete(self._header._next						)



      def 						SCREAMING_SNAKE_CASE_			(			self   :Dict						):
       if self.is_empty():
        raise IndexError('''remove_first from empty list'''						)
       return self._delete(self._trailer._prev						)



"""simple docstring"""


def     _lowerCamelCase(__UpperCamelCase       )				-> list:
	_lowerCAmelCase								=[True for i in range(n + 1       )]
	_lowerCAmelCase								=[i - 1 for i in range(n + 1       )]
	_lowerCAmelCase								=[]
	for i in range(2    , n + 1       ):
		if is_prime[i]:
			primes.append(__UpperCamelCase       )
		for j in range(0    , len(__UpperCamelCase       )       ):
			if i * primes[j] >= n:
				break
			_lowerCAmelCase								=False

			if i % primes[j] == 0:
				_lowerCAmelCase								=totients[i] * primes[j]
				break

			_lowerCAmelCase								=totients[i] * (primes[j] - 1)

	return totients


if __name__ == "__main__":
			import doctest

			doctest.testmod()



