





"""simple docstring"""


from math import pow




def 					lowercase__    (					lowercase_		,lowercase_		,lowercase_		,lowercase_		,lowercase_		,)					->		tuple[int, int]:




      """simple docstring"""

      if current_sum == needed_sum:
            # If the sum of the powers is equal to needed_sum, then we have a solution.
            solutions_count += 1
            return current_sum, solutions_count

      _UpperCamelCase      :	List[Any]						=       int(pow(lowercase_		,lowercase_			)			)
      if current_sum + i_to_n <= needed_sum:
            # If the sum of the powers is less than needed_sum, then continue adding powers.
            current_sum += i_to_n
            _UpperCamelCase,  _UpperCamelCase      :	Union[str, Any]						=       backtrack(
                lowercase_		,lowercase_		,current_number + 1		,lowercase_		,lowercase_			)
            current_sum -= i_to_n
      if i_to_n < needed_sum:
            # If the power of i is less than needed_sum, then try with the next power.
            _UpperCamelCase,  _UpperCamelCase      :	int						=       backtrack(
                lowercase_		,lowercase_		,current_number + 1		,lowercase_		,lowercase_			)
      return current_sum, solutions_count




def 					lowercase__    (					lowercase_		,lowercase_			)					->		int:




      """simple docstring"""

      if not (1 <= needed_sum <= 1_000 and 2 <= power <= 10):
            raise ValueError(
                "Invalid input\n"
                "needed_sum must be between 1 and 1000, power between 2 and 10."			)

      return backtrack(lowercase_		,lowercase_		,1		,0		,0			)[1]  # Return the solutions_count


if __name__ == "__main__":
  import doctest

  doctest.testmod()







"""simple docstring"""


from collections import defaultdict
from math import ceil, sqrt




def 					lowercase__    (					lowercase_ = 1_000_000		,lowercase_ = 10			)					->		int:




      """simple docstring"""

      _UpperCamelCase      :	defaultdict						=       defaultdict(lowercase_			)

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

            hole_width_lower_bound += (outer_width - hole_width_lower_bound) % 2

            for hole_width in range(lowercase_		,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() = }""")
