Count Distinct Prime Factors

You are given a sequence of n positive integers. For each integer, determine the number of distinct prime factors.

For example, the number 20 has the prime factorization \(20 = 2^2 \times 5\), so it has 2 distinct prime factors: 2 and 5.

You can use the Sieve of Eratosthenes to precompute the smallest prime factor \(\text{spf}[x]\) for each \(x\) up to \(10^6\). Then, for each integer, repeatedly divide by \(\text{spf}[x]\) while storing the distinct primes.

Input/Output: The input is read from stdin and the output is printed to stdout. See the input and output description for details.

inputFormat

The first line of input contains a single integer \(n\) representing the number of integers in the sequence. The second line contains \(n\) space-separated integers.

outputFormat

Output a single line with \(n\) space-separated integers, where each integer denotes the number of distinct prime factors of the corresponding input number.

## sample

1
13

1

</p>