output_description: Print the maximum number of integers that Snuke can circle.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
      s_1
      :
      s_N
attempt: def eratosthenes(n):
      isp = [True] * (n + 1)
      for i in range(2, n):
          if i * i > n:
              break
          if isp[i]:
              for i in range(i * 2, n + 1, i):
                  isp[i] = False
      return [i for i in range(2, n + 1) if isp[i]]
  
  
  MAX = 10**10 + 10
  MAX2 = int(MAX ** (1 / 2))
  MAX3 = int(MAX ** (1 / 3))
  prime = eratosthenes(MAX3)
  cubic = [i**3 for i in range(MAX2)]
  
  
  def normalize(n):
      for p in prime:
          while n % cubic[p] == 0:
              n //= cubic[p]
      return n
  
  
  def main():
      N = int(input())
      A = [int(input()) for _ in range(N)]
  
      res = 0
      mp = dict()
  
      for j, i in enumerate(A):
          i_norm = normalize(i)
          if i_norm == 1:
              res += 1
          else:
              if i_norm in mp:
                  mp[i_norm] += 1
              else:
                  mp[i_norm] = 1
  
      if res > 0:
          res = 1
  
      st = set()
      for k, v in mp.items():
          if k in st:
              continue
          st.add(k)
          k_rev = normalize(k**2)
          if k_rev in mp:
              res += max(v, mp[k_rev])
              st.add(k_rev)
          else:
              res += v
  
      print(res)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  Snuke got positive integers s_1,...,s_N from his mother, as a birthday
  present. There may be duplicate elements.
  
  He will circle some of these N integers. Since he dislikes cubic numbers, he
  wants to ensure that if both s_i and s_j (i ≠ j) are circled, the product
  s_is_j is _not_ cubic. For example, when s_1=1,s_2=1,s_3=2,s_4=4, it is not
  possible to circle both s_1 and s_2 at the same time. It is not possible to
  circle both s_3 and s_4 at the same time, either.
  
  Find the maximum number of integers that Snuke can circle.
samples: [{"input": "8\n    1\n    2\n    3\n    4\n    5\n    6\n    7\n    8", "output": "6\n    \n\nSnuke can circle 1,2,3,5,6,7.\n\n* * *"}, {"input": "6\n    2\n    4\n    8\n    16\n    32\n    64", "output": "3\n    \n\n* * *"}, {"input": "10\n    1\n    10\n    100\n    1000000007\n    10000000000\n    1000000009\n    999999999\n    999\n    999\n    999", "output": "9"}]