A cyber security firm has discovered a new type of encryption being used by a group of hackers. The encryption key will be a valid key, which is a number that has exactly 3 factors (or divisors). For example, 4 is a valid key because it has exactly 3 factors: 1, 2, and 4. But 6 is not a valid key because it has 4 factors: 1, 2, 3, and 6. Given an array keys of length n, find the number of valid keys in the range [1, keys[i], both inclusive, for each 0 <= i < n.

Constraints:

• 1 <= n <= 10^5
• 1 <= keys[i] <= 2.5 * 10^13

Input: An array of integers.

Output: An array of integers containing the answer for each query.