





"""simple docstring"""



from __future__ import annotations

from random import random






class 						__snake_case   :





 """simple docstring"""


 def __init__(       self   ,		__lowerCamelCase = None    ):



     '''simple docstring'''




     __A       :		Tuple							=	value
     __A       :		Tuple							=	random()
     __A       :		Node | None							=	None
     __A       :		Node | None							=	None

 def __repr__(       self    ):



     '''simple docstring'''




     from pprint import pformat

     if self.left is None and self.right is None:
         return F"""'{self.value}: {self.prior:.5}'"""
     else:
         return pformat(
             {F"""{self.value}: {self.prior:.5}""": (self.left, self.right)}   ,		indent=1    )







 def __str__(       self    ):



     '''simple docstring'''




     __A       :		int							=	str(self.value    ) + ''' '''
     __A       :		Dict							=	str(self.left or ''''''    )
     __A       :		List[Any]							=	str(self.right or ''''''    )
     return value + left + right







def 						__lowercase	(  snake_case_    :    Node | None							,snake_case_    :    int		)  ->tuple[Node | None, Node | None]:



    '''simple docstring'''







    if root is None:  # None tree is split into 2 Nones
        return None, None
    elif root.value is None:
        return None, None
    else:
        if value < root.value:
            __A					,			__A       :		Union[str, Any]							=	split(root.left							,snake_case_		)
            return left, root
        else:
            __A					,			__A       :		Tuple							=	split(root.right							,snake_case_		)
            return root, right







def 						__lowercase	(  snake_case_    :    Node | None							,snake_case_    :    Node | None		)  ->Node | None:



    '''simple docstring'''







    if (not left) or (not right):  # If one node is None, return the other
        return left or right
    elif left.prior < right.prior:
        __A       :		Any							=	merge(left.right							,snake_case_		)
        return left
    else:
        __A       :		List[str]							=	merge(snake_case_							,right.left		)
        return right







def 						__lowercase	(  snake_case_    :    Node | None							,snake_case_    :    int		)  ->Node | None:



    '''simple docstring'''







    __A       :		int							=	Node(snake_case_		)
    __A					,			__A       :		Optional[Any]							=	split(snake_case_							,snake_case_		)
    return merge(merge(snake_case_							,snake_case_		)							,snake_case_		)







def 						__lowercase	(  snake_case_    :    Node | None							,snake_case_    :    int		)  ->Node | None:



    '''simple docstring'''







    __A					,			__A       :		Union[str, Any]							=	split(snake_case_							,value - 1		)
    __A					,			__A       :		Union[str, Any]							=	split(snake_case_							,snake_case_		)
    return merge(snake_case_							,snake_case_		)







def 						__lowercase	(  snake_case_    :    Node | None		)  ->None:



    '''simple docstring'''







    if not root:  # None
        return
    else:
        inorder(root.left		)
        print(root.value							,end=''','''		)
        inorder(root.right		)







def 						__lowercase	(  snake_case_    :    Node | None							,snake_case_    :    str		)  ->Node | None:



    '''simple docstring'''







    for arg in args.split():
        if arg[0] == "+":
            __A       :		Optional[Any]							=	insert(snake_case_							,int(arg[1:]		)		)

        elif arg[0] == "-":
            __A       :		str							=	erase(snake_case_							,int(arg[1:]		)		)

        else:
            print('''Unknown command'''		)

    return root







def 						__lowercase	(  )  ->None:



    '''simple docstring'''







    __A       :		Dict							=	None
    print(
        '''enter numbers to create a tree, + value to add value into treap, '''
        '''- value to erase all nodes with value. \'q\' to quit. '''		)

    __A       :		str							=	input()
    while args != "q":
        __A       :		List[Any]							=	interact_treap(snake_case_							,snake_case_		)
        print(snake_case_		)
        __A       :		Optional[Any]							=	input()

    print('''good by!'''		)


if __name__ == "__main__":
       import doctest

       doctest.testmod()
       main()











"""simple docstring"""



from collections import defaultdict
from math import gcd







def 						__lowercase	(  snake_case_    :    int = 1500000		)  ->int:



    '''simple docstring'''







    __A       :		defaultdict							=	defaultdict(snake_case_		)
    __A       :		Any							=	2
    while 2 * euclid_m * (euclid_m + 1) <= limit:
        for euclid_n in range((euclid_m % 2) + 1							,snake_case_							,2		):
            if gcd(snake_case_							,snake_case_		) > 1:
                continue
            __A       :		List[Any]							=	2 * euclid_m * (euclid_m + euclid_n)
            for perimeter in range(snake_case_							,limit + 1							,snake_case_		):
                frequencies[perimeter] += 1
        euclid_m += 1
    return sum(1 for frequency in frequencies.values() if frequency == 1		)


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




