問題文

Nの素因数の種類の数を求めよ。 問題はQ個与えられる。

制約

• $2 \leq N \leq 10^6$
• $1 \leq Q \leq 2*10^5$

入力

入力は以下の形式で標準入力から与えられる

Q
N_1
N_2
...
N_q

サンプル

5
16
24
23
57
2310

1
2
1
2
5

• 16=2⁴であるので素因数の種類は「2」だけで個数は1です。
• 24=2³×3であるので素因数の種類は「2,3」で個数は2です。
• 23は素数なので素因数の種類は「23」で個数は1です。
• 57=3×19なので素因数の種類は「3,19」で個数は2です。57は素数ではありません。
• 2310=2×3×5×7×11であるため素因数の種類は「2,3,5,7,11」で個数は5です。