import std.stdio;
import std.conv, std.array, std.algorithm, std.string;
import std.math, std.random, std.range, std.datetime;
import std.bigint;

void main(){
	
	int n = readln.chomp.to!int;
	long[] ss;
	for(int i = 0; i < n; i ++){
		ss ~= readln.chomp.to!long;
		}
	
	int[] primes, prime2s, prime3s;
	bool[] flags = new bool[100_009];
	for(int i = 2; i < flags.length; i ++){
		if(!flags[i]){
			primes ~= i;
			prime2s ~= i * i;
			prime3s ~= i * i * i;
			for(int j = i; j < flags.length; j += i) flags[j] = 1;
			}
		}
	
	int[long] count, anticount;
	
	foreach(s; ss){
		long x = 1, y = 1;
		for(int i = 0; i < primes.length; i ++){
			while(s % prime3s[i] == 0) s /= prime3s[i];
			if(s % prime2s[i] == 0){
				x *= prime2s[i];
				y *= primes[i];
				s /= prime2s[i];
				}
			else if(s % primes[i] == 0){
				x *= primes[i];
				y *= prime2s[i];
				s /= primes[i];
				}
			if(s < primes[i]) break;
			}
		
		if(s > 1) continue; // s is prime
		
		if(x <= y) count[x] += 1;
		else anticount[y] += 1;
		}
	
	int ans = n;
	
	foreach(x; count.keys){
		if(x == 1) ans -= count[x] - 1;
		if(!(x in anticount)) continue;
		if(count[x] > anticount[x]) ans -= anticount[x];
		else ans -= count[x];
		}
	
	/*
	count.writeln;
	"-".writeln;
	anticount.writeln;
	*/
	
	ans.writeln;
	
	}