№23 — #23158

from functools import lru_cache
import math
def is_square(n):
    r = int(math.isqrt(n))
    return r * r == n
def cube_root_int(n):
    r = round(n ** (1 / 3))
    while (r + 1) ** 3 <= n:
        r += 1
    while r ** 3 > n:
        r -= 1
    return r if r ** 3 == n else None
def sum_digits(n):
    return sum(map(int, str(n)))
@lru_cache(None)
def f(n, has125=False, has25=False, last='', streak=0):
    if n == 5:
        return 1 if (has125 or has25) else 0
    if n < 5 or n == 24:
        return 0
ans = 0
    moves = [('A', n - 5)]
if is_square(n):
        x = int(math.isqrt(n))
        if x < n:
            moves.append(('B', x))
r = cube_root_int(n)
    if r is not None and r < n:
        moves.append(('C', r))
if n > 9:
        x = n // 10
        if x < n:
            moves.append(('D', x))
x = n // 2 if n % 2 == 0 else n - 7
    if x < n and x >= 1:
        moves.append(('E', x))
for cmd, nxt in moves:
        ns = streak + 1 if cmd == last else 1
        if ns <= 2:
            ans += f(nxt, has125 or nxt == 125, has25 or nxt == 25, cmd, ns)
return ans
raw = f(500)
print(sum_digits(raw) ** 2)