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: """
  Rを立法数とする
  a * R と a**2 * R は片方だけ取れる
  →Rを取り除いて後はDP
  
  どうやって立法数を取り除く？
  10**3.3まで試し割り？→5secだから間に合うかなぁ
  """
  
  N = int(input())
  
  mul3s = []
  i = 2
  while i**3 <= 10**10:
      mul3s.append(i**3)
      i += 1
  
  div3 = []
  
  dic = {}
  div2 = []
  
  for i in range(N):
  
      s = int(input())
  
      for j in mul3s:
          while s % j == 0:
              s //= j
          if s < j:
              break
  
      if s == 1:
          div3.append(s)
      elif s not in dic:
          dic[s] = 1
          div2.append(s)
      else:
          dic[s] += 1
  
  div2.sort()
  
  pdic = {}
  dpdic = {}
  
  for i in div2:
  
      if (int(i**0.5) ** 2 == i and int(i**0.5) not in dic) or int(i**0.5) ** 2 != i:
          dpdic[i] = [dic[i]]
          pdic[i] = i
      else:
          dpdic[pdic[int(i**0.5)]].append(dic[i])
          pdic[i] = pdic[int(i**0.5)]
  
  # print (dpdic)
  
  ans = min(1, len(div3))
  
  for nlis in dpdic:
  
      dp = [0] * 2  # 0=前の奴を使ってない 1=使った
  
      for i in dpdic[nlis]:
          ndp = [0] * 2
          ndp[0] = max(dp[0], dp[1])
          ndp[1] = dp[0] + i
          dp = ndp
  
      ans += max(dp)
  
  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"}]