erase(p, x) = {
	rem /= p^x;
	if (x>1 && bitand(valuation(rem, p), x/2),
		erase(p, x/2);
	);
	if (bitand(valuation(rem, p), x*2),
		erase(p, x*2);
	);
	if (p>2,
		my (o=precprime(p-1));
		if (bitand(valuation(rem, o), x),
			erase(o, x);
		);
	);
	my (q=nextprime(p+1));
	if (bitand(valuation(rem, q), x),
		erase(q, x);
	);
}

a(n) = {
	my (k=0, f=factor(n), i=1);
	rem = n;
	while (rem>1,
		my (p=f[i,1], v=valuation(rem, p));
		if (v,
			my (x=2^valuation(v, 2));
			erase(p, x);
			k++,
			i++;
		);
	);
	return (k);
}

for (n=1, 10 000, print (n " " a(n)))

quit