解题思路

题意： 定义正整数 $n$ 的权值为其正因子的数量，即

题目内容

定义正整数 $n$ 的权值为 $n$ 的正因子的数量，即 $wt(n)=\tau(n)$ ，其中 $\tau(n)$ 表示 $n$ 的因子个数。

给定一个正整数 $x$ ，你可以将 $x$ 分解为若干个大于 $1$ 的正整数 $p_1,p_2,…,p_n(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$ .