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 get_sieve_of_eratosthenes_new(n):
      import math
  
      if not isinstance(n, int):
          raise TypeError("n is int type.")
      if n < 2:
          raise ValueError("n is more than 2")
      prime = []
      limit = math.sqrt(n)
      data = [i + 1 for i in range(1, n)]
      while True:
          p = data[0]
          if limit <= p:
              return prime + data
          prime.append(p)
          data = [e for e in data if e % p != 0]
  
  
  prime = get_sieve_of_eratosthenes_new(2160)
  
  
  def ind(b, n):
      res = 0
      while n % b == 0:
          res += 1
          n //= b
      return res
  
  
  import sys
  
  input = sys.stdin.readline
  
  N = int(input())
  dic = {}
  inverse = {}
  for i in range(N):
      s = int(input())
      S = s**2
      for p in prime:
          a = ind(p, s)
          s //= p ** (a - a % 3)
          S //= p ** (2 * a - (2 * a) % 3)
      if s not in dic:
          dic[s] = 0
          inverse[s] = 0
      dic[s] += 1
      inverse[s] = S
  
  one = 0
  double = 0
  for i in dic:
      if i != 1:
          if inverse[i] in dic:
              double += max(dic[i], dic[inverse[i]])
          else:
              one += dic[i]
  
  double //= 2
  ans = one + double
  if 1 in dic:
      ans += 1
  print(ans)
  
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"}]