3B.py

from collections import defaultdict
import sys

N = int(sys.stdin.readline())

grid = defaultdict(lambda: 0)
grid[0, 0] = 1
x, y = 0, 0
dx, dy = 1, 0
while grid[x, y] <= N:
  x += dx
  y += dy
  grid[x, y] = sum(
      grid[nx, ny]
      for nx in (x - 1, x, x + 1)
      for ny in (y - 1, y, y + 1))
  if grid[x - dy, y + dx] == 0:
    dx, dy = -dy, dx
print(grid[x, y])