import Data.Function (on)
import Data.List (foldl', sortBy)
import qualified Data.Set as Set

main :: IO ()
main = print . solve . map read . tail . lines =<< getContents

solve :: [Integer] -> Int
solve xs = fst $ foldl' f (0, Set.empty) ys
  where ys = sortBy (compare `on` (length . snd)) [ (x, [ y | y <- xs, isCube (x * y) ]) | x <- xs ]
        f (k, sy) (c, zs) | Set.member c sy = (k, sy)
                          | otherwise = (k + 1, Set.fromList zs `Set.union` sy)

isCube :: Integral a => a -> Bool
isCube x = round (fromIntegral x ** (1.0/3)) ^ 3 == x
