






"""simple docstring"""





from __future__ import annotations







def   lowerCAmelCase_( SCREAMING_SNAKE_CASE ,	SCREAMING_SNAKE_CASE					)					->	bool:
    """simple docstring"""

    UpperCamelCase__         =    get_failure_array(SCREAMING_SNAKE_CASE					)

    # 2) Step through text searching for pattern
    UpperCamelCase__       ,						UpperCamelCase__         =    0, 0  # index into text, pattern
    while i < len(SCREAMING_SNAKE_CASE					):
        if pattern[j] == text[i]:
            if j == (len(SCREAMING_SNAKE_CASE					) - 1):
                return True
            j += 1

        # if this is a prefix in our pattern
        # just go back far enough to continue
        elif j > 0:
            UpperCamelCase__         =    failure[j - 1]
            continue
        i += 1
    return False







def   lowerCAmelCase_( SCREAMING_SNAKE_CASE					)					->	list[int]:
    """simple docstring"""

    UpperCamelCase__         =    [0]
    UpperCamelCase__         =    0
    UpperCamelCase__         =    1
    while j < len(SCREAMING_SNAKE_CASE					):
        if pattern[i] == pattern[j]:
            i += 1
        elif i > 0:
            UpperCamelCase__         =    failure[i - 1]
            continue
        j += 1
        failure.append(SCREAMING_SNAKE_CASE					)
    return failure


if __name__ == "__main__":
  # Test 1)
  A__					: Dict=	"""abc1abc12"""
  A__					: int=	"""alskfjaldsabc1abc1abc12k23adsfabcabc"""
  A__					: Any=	"""alskfjaldsk23adsfabcabc"""
  assert kmp(pattern, texta) and not kmp(pattern, texta)

  # Test 2)
  A__					: Optional[Any]=	"""ABABX"""
  A__					: Union[str, Any]=	"""ABABZABABYABABX"""
  assert kmp(pattern, text)

  # Test 3)
  A__					: List[str]=	"""AAAB"""
  A__					: Tuple=	"""ABAAAAAB"""
  assert kmp(pattern, text)

  # Test 4)
  A__					: Any=	"""abcdabcy"""
  A__					: Dict=	"""abcxabcdabxabcdabcdabcy"""
  assert kmp(pattern, text)

  # Test 5)
  A__					: str=	"""aabaabaaa"""
  assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]












"""simple docstring"""





from collections import defaultdict
from math import ceil, sqrt







def   lowerCAmelCase_( SCREAMING_SNAKE_CASE = 1_00_00_00 ,	SCREAMING_SNAKE_CASE = 10					)					->	int:
    """simple docstring"""

    UpperCamelCase__         =    defaultdict(SCREAMING_SNAKE_CASE					)

    for outer_width in range(3 ,	(t_limit // 4) + 2					):
        if outer_width * outer_width > t_limit:
            UpperCamelCase__         =    max(
                ceil(sqrt(outer_width * outer_width - t_limit					)					) ,	1					)
        else:
            UpperCamelCase__         =    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 <= 10					)


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




