Count Unique Prime Factors

You are given a list of n integers. For each integer n, you are required to calculate the number of unique prime factors in its prime factorization. Formally, for a positive integer \(n\) (where \(n > 1\)) with prime factorization \(n = \prod_{i=1}^{k} p_i^{a_i}\), the answer is \(k\). Note that if \(n = 1\), it has no prime factors so the answer is 0.

Your task is to compute and output the unique prime factors count for each element in the input list.

inputFormat

The first line of input contains a single integer n representing the number of integers. The second line contains n space-separated integers.

outputFormat

Output n integers separated by spaces. The i-th integer should represent the number of unique prime factors of the i-th input number.

4
10 15 21 28

2 2 2 2