Различные простые по запросам

Для каждого из $q$ чисел выведите количество различных простых делителей этого числа.

В первой строке число $q$ от $1$ до $10^5$. Во второй — $q$ чисел от $1$ до $10^6$.

$q$ чисел через пробел.

Заметьте, что если в решете идти по каждому простому и добавлять единицу всем его кратным, то каждое число получит ровно столько единиц, сколько у него различных простых делителей.