We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Leonardo's Prime Factors

Leonardo's Prime Factors

Leonardo loves primes and created queries where each query takes the form of an integer, . For each , count the maximum number of distinct prime factors of any number in the inclusive range .

Note: Recall that a prime number is only divisible by and itself, and is not a prime number.

Example

The maximum number of distinct prime factors for values less than or equal to is . One value with distinct prime factors is . Another is .

Function Description

Complete the primeCount function in the editor below.

primeCount has the following parameters:

  • int n: the inclusive limit of the range to check

Returns

  • int: the maximum number of distinct prime factors of any number in the inclusive range .

Input Format

The first line contains an integer, , the number of queries.
Each of the next lines contains a single integer, .

Constraints

Sample Input

6
1
2
3
500
5000
10000000000

Sample Output

0
1
1
4
5
10

Explanation

  1. is not prime and its only factor is itself.
  2. has prime factor, .
  3. The number has prime factor, , has and has prime factors.
  4. The product of the first four primes is . While higher value primes may be a factor of some numbers, there will never be more than distinct prime factors for a number in this range.