409996: GYM103895 F Rats Rats

F. Rats Ratstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Gregorio is building a rat army! By themselves, rats are small and fairly weak. However, they have a secret ability: in the midst of battle, they can call upon reinforcements, causing a rat swarm!

Gregorio finds it difficult to keep track of each rat during battle, especially since they keep calling for reinforcements. As a result, he only knows the total number of rats after the battle is won (Gregorio always wins).

In particular, the rats summon reinforcements in an orderly way, so Gregorio knows the total number of rats is always a perfect power. A perfect power is a number $$$y$$$ such that there exist integers $$$x, k$$$ where $$$y = x^k$$$, $$$k > 1$$$.

However, for any given $$$y$$$, there may be multiple values $$$x, k$$$ that satisfy the criteria. Gregorio has several different rat species, and he uses exactly one species for each battle. Each species corresponds to a single value $$$x$$$ which is the same for a given species across all battles.

Raising different species is expensive, so Gregorio tries to have as few rat species as possible. Gregorio has a list of battles that he has won, along with the final number of rats for each (a perfect power). Now he wants to know: between all the battles, what's the minimum number of rat species he could own and still be consistent with the battle data?

Input

The first line contains one integer $$$N$$$ representing the number of battles. ($$$1 \le N \le 10^5$$$)

The next line contains $$$N$$$ integers $$$a_1, a_2, ... , a_n$$$ representing the final number of rats after each battle. It is guaranteed that each $$$a_i$$$ is a perfect power. ($$$1 \le a_i \le 10^9$$$)

Output

Print out a single integer, the minimum number of rat species Gregorio could own which is consistent with the battle data. In other words, the minimum number of distinct values $$$x_1, x_2, ...$$$ such that for each $$$a_i$$$, there is some $$$x_j$$$ and some other integer $$$k$$$ such that $$$a_i = x_j^k$$$.

ExampleInput

5
512 64 243 25 32768

Output

3

Note

In the example:

• $$$512 = 8^3$$$
• $$$64 = 8^2$$$
• $$$243 = 3^5$$$
• $$$25 = 5^2$$$
• $$$32768 = 8^5$$$

This corresponds to 3 distinct values for $$$x$$$: 3, 5, and 8. It can be shown that this is the minimum possible number of distinct $$$x$$$ values.