№23 — #23140

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, last='', streak=0, has8=False, has64=False):
    if n == 1:
        return 1 if (has8 ^ has64) else 0
    if n < 1:
        return 0
ans = 0
moves = [('A', n - 1)]
if is_square(n):
        r = int(math.isqrt(n))
        if r < n:
            moves.append(('B', r))
r = cube_root_int(n)
    if r is not None and r < n:
        moves.append(('C', r))
if n > 9:
        moves.append(('D', n // 10))
x = n // 2 if n % 2 == 0 else n - 3
    if x >= 1 and x < n:
        moves.append(('E', x))
for cmd, nxt in moves:
        new_streak = streak + 1 if cmd == last else 1
        if new_streak <= 2:
            ans += f(nxt, cmd, new_streak, has8 or nxt == 8, has64 or nxt == 64)
return ans
raw = f(512)
print(sum_digits(raw) ** 2)