def monicpoly(n, d) :
  """return, as a list of coefficients, constant term last,
  nth height 1 monic polynomial of degree d with nonzero constant term"""
  n, r = divmod(n, 2)
  p = [2*r-1]
  for _ in range(d-1) :
    n, r = divmod(n, 3)
    p.append(r-1)
  if n :
    raise ValueError('n too big')
  p.append(1)
  p.reverse()
  return p

def height1(d) :
  """generate all* monic height 1 polys p of degree d with p(x) != 0
  polys are returned in lexicographical increasing or decreasing order
  *If a poly has a lexicographically less equivalent, skip it."""
  if d < 2 :
    yield [1, -1] if d else [1]
    return
  for n in range(4*3**(d-2)) :
    p = monicpoly(n, d)
    # see if there are lexicographically less equivalents
    c = 0
    for i in range(1, d+1, 2) :
      if not p[i] : continue
      c = p[i] > 0
      break
    if c : continue    # x->-x (but monic) is lexicographically less
    if p[-1] > 0 :
      for i in range(1, d//2+1) :
        if p[i] == p[d-i] : continue
        c = p[i] > p[d-i]
        break
      if c : continue    # x->1/x (but monic) is lexicographically less
      for i in range(1, d, 2) :
        if p[i] != -p[d-i] :
          c = p[i] > -p[d-i]
          break
        if p[i+1] == p[d-i-1] : continue
        c = p[i+1] > p[d-i-1]
        break
    else :
      for i in range(1, d//2+1) :
        if p[i] == -p[d-i] : continue
        c = p[i] > -p[d-i]
        break
      if c : continue    # x->1/x (but monic) is lexicographically less
      for i in range(1, d, 2) :
        if p[i] != p[d-i] :
          c = p[i] > p[d-i]
          break
        if p[i+1] == -p[d-i-1] : continue
        c = p[i+1] > -p[d-i-1]
        break
    if c : continue    # x->-1/x (but monic) is lexicographically less
    yield p

def a(n) :
  c = 0
  for p in height1(n) : c+=1
  return c