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