题目描述

小 F 想考你一个很简单的数论问题，给出一个数 $x$ ，定义 $f(x)$ 为 $x$ 的不同质因子个数，例如 $f(12)=2$ 。

$q$ 次询问，每次给出一个数 $x$ ，要求输出 $f(x)$ 。

输入格式

第一行一个整数 $q$ 表示询问次数。

接下来 $q$ 行每行一个整数 $x_i$ ($2\leq x_i\leq 10^6$) ，表示一组询问。

输出格式

输出 $q$ 行，每行一个整数表示 $f(x_i)$ 。

样例

3
12 
30030 
2333

2
6
1

数据范围与约定

对于 $20\%$ 的数据， $q\leq 10$ 。

对于 $40\%$ 的数据， $q\leq 1000$ 。

对于另外 $20\%$ 的数据， $x_i\leq 1000$ 。

对于 $100\%$ 的数据， $q\leq 10^6$ 。