You are given a sequence of non-negative numbers and you are required to put some of these numbers into a bucket such that:

The product of any two distinct elements in the bucket is not a cube and the numbers in the bucket must be maximum.

Now, your task is to determine the maximum number of elements in the bucket.

Input format

• The first line contains a single integer $N$.
• Each of the next $N$ lines contains elements of the sequence

Output format

Print the maximum number of elements in the bucket

Constraints

$1 \le N \le 1e5\\ 1 \le A_i \le 10^{10}$