

from __future__ import annotations

from random import choice


def 					A__	(       SCREAMING_SNAKE_CASE_		)   ->     Dict:
		return choice(lowerCamelCase_		)


def 					A__	(       SCREAMING_SNAKE_CASE_							,       SCREAMING_SNAKE_CASE_		)   ->     Union[str, Any]:
		lowerCamelCase   : Any								=random_pivot(lowerCamelCase_		)

		# partition based on pivot
		# linear time
		lowerCamelCase   : Any								=[e for e in lst if e < pivot]
		lowerCamelCase   : Dict								=[e for e in lst if e > pivot]

		# if we get lucky, pivot might be the element we want.
		# we can easily see this:
		# small (elements smaller than k)
		# + pivot (kth element)
		# + big (elements larger than k)
		if len(lowerCamelCase_		) == k - 1:
				return pivot
		# pivot is in elements bigger than k
		elif len(lowerCamelCase_		) < k - 1:
				return kth_number(lowerCamelCase_							,       k - len(lowerCamelCase_		) - 1		)
		# pivot is in elements smaller than k
		else:
				return kth_number(lowerCamelCase_							,       lowerCamelCase_		)


if __name__ == "__main__":
				import doctest

				doctest.testmod()








from collections import defaultdict
from math import ceil, sqrt


def 					A__	(       SCREAMING_SNAKE_CASE_ = 1_0_0_0_0_0_0							,       SCREAMING_SNAKE_CASE_ = 1_0		)   ->     int:
		lowerCamelCase   : defaultdict								=defaultdict(SCREAMING_SNAKE_CASE_		)

		for outer_width in range(3							,       (t_limit // 4) + 2		):
				if outer_width * outer_width > t_limit:
						lowerCamelCase   : Any								=max(
						    ceil(sqrt(outer_width * outer_width - t_limit		)		)							,       1		)
				else:
						lowerCamelCase   : str								=1

				hole_width_lower_bound += (outer_width - hole_width_lower_bound) % 2

				for hole_width in range(SCREAMING_SNAKE_CASE_							,       outer_width - 1							,       2		):
						count[outer_width * outer_width - hole_width * hole_width] += 1

		return sum(1 for n in count.values() if 1 <= n <= 1_0		)


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

