U93191 小凯的函数

众所周知，小凯对数学有独特的情感，现在他又在学习数学。

小凯发现了一个好玩的函数，小凯给它命名为“小凯的质函数”。 “小凯的质函数”： - $g(x)$的定义域为$\{x∈Z|x \geqslant 1\}$， - $g(x \times y)=g(x)+g(y)$， - $g(1)=0$， - 当 $x$ 为质数时有 $g(x)=1$。 $g(x)$ 即为“小凯的质函数”。 现在，小凯要问你 $n$ 个问题，你的麻烦来了。

第一行，一个正整数 $n$，表示问题的个数。 接下来 $n$ 行，每行一个整数 $a$，你要求出 $g(a)$ 并输出。

对于每一个$a$，输出 $g(a)$。 每个输出占一行。

样例一： $g(4)=g(2)+g(2)=1+1=1$，$g(3)=1$，$g(5)=1$ 。 --- 对 $50\%$ 的数据 $n \leqslant 100$。 对 $100\%$ 的数据 $n \leqslant 2000$, $1\leqslant a \leqslant 10$$^1$$^2$。 --- 补充：对于任意一个数据点，其中的绝大部分数字是在某一区间范围内随机生成的。