思路

考虑一下有多种质因子和一种质因子的情况。

• 只有一种质因子 $a$

  $x=a^y$， 假设拆成了 $a^{p_1}, a^{p_2},...,a^{p_k}$ ，那么这 $k$ 个数的因子数总和为 $\sum_{i=1}^k (p_i+1)=k+\sum_{i=1}^k p_i=k+y$

  所以需要 $k$ 越大越好，就是将 $x$ 拆分为 $y$ 个 $a$ 即可，此时答案是 $2y$

题目描述

小红定义一个数字的权值为:该数字的因子个数。

小红现在拿到了一个正整数，他希望将:分解为若干不等于1的数字(也可以不做分解)，使得所有分解出的正整数乘积等于$x$，且所有数字的权值之和尽可能大，你能帮帮他求出最大的权值吗。

输入描述

输入包含$T 十1$行。 第一行一个正整数 $T(1\le T\le 10^4)$，表示数据组数。

接下来$T$行，每行一个正整数$x(2 \le x \le 2\times 10^5)$，表示每组数据中小红询问的数字$x$。

输出描述

输出包含$T$ 行，每行一个正整数表示每组测试数据的最大权值和

样例

输入

3
2
10
123

输出

2
4
4

说明

第一个测试数据中，无法分解，直接取2的权值为 2.
第二个测试数据中，将 10 分解为 2x5，权值和为 4。