


'''simple docstring'''



from collections.abc import Sequence
from queue import Queue





class   UpperCAmelCase_    :





    """simple docstring"""






    def __init__(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_=None     ,	SCREAMING_SNAKE_CASE_=None      )							->	int:
         __lowerCamelCase  :      str														=						start
         __lowerCamelCase  :      Union[str, Any]														=						end
         __lowerCamelCase  :      Any														=						val
         __lowerCamelCase  :      int														=						(start + end) // 2
         __lowerCamelCase  :      str														=						left
         __lowerCamelCase  :      Tuple														=						right







    def __repr__(				self      )							->	List[str]:
         return f'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'







class   UpperCAmelCase_    :





    """simple docstring"""






    def __init__(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	List[Any]:
         __lowerCamelCase  :      Optional[Any]														=						collection
         __lowerCamelCase  :      Tuple														=						function
         if self.collection:
              __lowerCamelCase  :      List[str]														=						self._build_tree(0     ,	len(SCREAMING_SNAKE_CASE_      ) - 1      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	List[Any]:
         self._update_tree(self.root     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	Optional[Any]:
         return self._query_range(self.root     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	Union[str, Any]:
         if start == end:
              return SegmentTreeNode(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	self.collection[start]      )
         __lowerCamelCase  :      Optional[int]														=						(start + end) // 2
         __lowerCamelCase  :      str														=						self._build_tree(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
         __lowerCamelCase  :      List[Any]														=						self._build_tree(mid + 1     ,	SCREAMING_SNAKE_CASE_      )
         return SegmentTreeNode(SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	self.fn(left.val     ,	right.val      )     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	List[str]:
         if node.start == i and node.end == i:
              __lowerCamelCase  :      Any														=						val
              return
         if i <= node.mid:
              self._update_tree(node.left     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
         else:
              self._update_tree(node.right     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
         __lowerCamelCase  :      Any														=						self.fn(node.left.val     ,	node.right.val      )







    def  lowercase_							(				self     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )							->	List[Any]:
         if node.start == i and node.end == j:
              return node.val

         if i <= node.mid:
              if j <= node.mid:
                   # range in left child tree
                   return self._query_range(node.left     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )
              else:
                   # range in left child tree and right child tree
                   return self.fn(
                       self._query_range(node.left     ,	SCREAMING_SNAKE_CASE_     ,	node.mid      )     ,	self._query_range(node.right     ,	node.mid + 1     ,	SCREAMING_SNAKE_CASE_      )     ,	)
         else:
              # range in right child tree
              return self._query_range(node.right     ,	SCREAMING_SNAKE_CASE_     ,	SCREAMING_SNAKE_CASE_      )







    def  lowercase_							(				self      )							->	Dict:
         if self.root is not None:
              __lowerCamelCase  :      Any														=						Queue()
              queue.put(self.root      )
              while not queue.empty():
                   __lowerCamelCase  :      List[str]														=						queue.get()
                   yield node

                   if node.left is not None:
                        queue.put(node.left      )

                   if node.right is not None:
                        queue.put(node.right      )


if __name__ == "__main__":
      import operator

      for fn in [operator.add, max, min]:
            print("""*""" * 50)
            A__						:   List[Any]				=    SegmentTree([2, 1, 5, 3, 4], fn)
            for node in arr.traverse():
                  print(node)
            print()

            arr.update(1, 5)
            for node in arr.traverse():
                  print(node)
            print()

            print(arr.query_range(3, 4))  # 7
            print(arr.query_range(2, 2))  # 5
            print(arr.query_range(1, 3))  # 13
            print()










'''simple docstring'''



from collections import defaultdict
from math import gcd



def      UpperCAmelCase__   (      UpperCAmelCase_       :							int = 1_50_00_00				)	->						int:
     __lowerCamelCase  :      defaultdict														=						defaultdict(UpperCAmelCase_				)
     __lowerCamelCase  :      Any														=						2
     while 2 * euclid_m * (euclid_m + 1) <= limit:
          for euclid_n in range((euclid_m % 2) + 1 ,       UpperCAmelCase_ ,       2				):
               if gcd(UpperCAmelCase_ ,       UpperCAmelCase_				) > 1:
                    continue
               __lowerCamelCase  :      Any														=						2 * euclid_m * (euclid_m + euclid_n)
               for perimeter in range(UpperCAmelCase_ ,       limit + 1 ,       UpperCAmelCase_				):
                    frequencies[perimeter] += 1
          euclid_m += 1
     return sum(1 for frequency in frequencies.values() if frequency == 1				)


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






