核心结论

设

$x=\prod_{i=1}^{m} q_i^{a_i}$

是 $x$ 的质因数分解，其中：

• $q_i$ 是 $x$ 的第 $i$ 个 不同质因子；

题目内容

定义正整数 $n$ 的权值为 $n$ 的正因子的数量，即 $wt(n)=r(n)$ ，

其中 $r(n)$ 表示 $n$ 的因子个数。

给定一个正整数 $x$ ，你可以将 $x$ 分解为若干个大于 $1$ 的正整数 $p_1,p_2,...,p(k≥1)$ ，要求

• $p_1×p_2×...×p_k=x$

• 最大化 $\sum^k_{i=1}wt(p_i)$

请你求出在最优分解下，上述表达式的最大可能值。

输入描述

第一行输入一个整数 $T(1 ≤ T ≤ 10^4)$ 表示测试数据组数。

此后 $T$ 行，每行输入一个整数 $x(2 ≤x≤2×10^5)$ 。

输出描述

对于每组数据，在一行上输出对应的最大权值和。

样例1

输入

3
2
10
123

输出

2
4
4

说明

• 对于 $x = 2$ ，无法再分解，只能取自身，$wt(2)= 2$ 。

• 对于 $x=10$ ，最优方案为 $10=2×5$ ，$wt(2)=2，wt(5)=2$ ，总和 $2+2=4$ 。

• 对于 $x=123$ ，最优方案为 $123=3×41,wt(3)=2，wt(41)=2$ ，总和 $4$ 。