Count Distinct Prime Factors

Given a list of positive integers, your task is to determine the number of distinct prime factors for each integer. For any integer ( n ), you need to count how many different prime numbers divide ( n ). Note that by convention, the number 1 has no prime factors.

For example, consider ( n = 10 ). The prime factors are 2 and 5, so the answer is 2. Similarly, for ( n = 8 ) (which can be written as (2^3)), there is only one distinct prime factor (2).

inputFormat

Input is given from standard input. The first line contains an integer ( n ) (the number of integers). The second line contains ( n ) space‐separated positive integers.

outputFormat

Print a single line to standard output containing ( n ) integers. Each integer is the count of distinct prime factors for the corresponding input number, separated by a space.## sample

1
10

2