描述

曹操为了在赤壁之战中战胜刘备和孙权，他立下了一个\(flag\)：如果打不败刘备和孙权，就出一道数学题给大臣们做！然后，赤壁之战他就输了。他想了这样一个数学题：\(f[x]=x\)的不同的质因数的数量，求出\(a_i\)的\(f[a_i]\)。

格式

输入格式

第一行一个正整数，表示\(n\)个数求\(f[a_i]\)；
接下来\(n\)行，每行一个正整数\(a_i\)。

输出格式

对于每一个\(a_i\)，给出\(f[a_i]\)。

样例1

输入样例1

3
12
30030
2333

输出样例1

2
6
1

限制

对于\(100\)%的数据，\(n≤30000，a_i≤30000\)。

来源

地址；\(vijos\)，芜湖\(OI\)团队
作者：黑暗路西法\(08\)
模拟赛\(T3\)