题目内容

给定一个正整数 $n$，考虑将其表示为三个正整数 $a,b,c$ 的乘积，即 $a \times b \times c = n$，并且要求 $a,b,c$ 两两互质（即 $\gcd(a,b)=\gcd(b,c)=\gcd(a,c)=1$）。在所有满足条件的 $(a,b,c)$ 中，请找出 $a+b+c$ 的最小值。注意，允许其中某些数为 $1$。

本题包含多组测试数据，每组数据给出一个 $n$，你需要输出对应的最小和。

约束：测试数据组数 $T$ 满足 $1 \le T \le 2\times 10^5$，每个 $n$ 满足 $1 \le n \le 10^7$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来 $T$ 行，每行包含一个整数 $n$。

输出描述

对于每组测试数据，输出一行一个整数，表示最小的 $a+b+c$。

样例1

输入

3
2
8
18

输出

4
10
12

说明

对于 $n=2$，只有质因子 $2$，三元组只能为 $(2,1,1)$，和为 4。 对于 $n=8=2^3$，质因子幂为 $8$，须完整分配，得 $(8,1,1)$，和为 10。 对于 $n=18=2 \times 3^2$，质因子幂为 $2$ 与 $9$，须分入不同数，得 $(2,9,1)$，和为 12。

样例2

输入

3
1
105
210

输出

3
15
18

说明

对于 $n=1$，只有一种拆分 $(1,1,1)$，和为 3。 对于 $n=105=3 \times 5 \times 7$，三个质因子各自独立，可分别放入 $a,b,c$，得 $(3,5,7)$，和为 15。 对于 $n=210=2 \times 3 \times 5 \times 7$，四个质因子部分为 $2,3,5,7$。为使和最小，应将较小的两个质因子合并，得 $(6,5,7)$，和为 $6+5+7=18$，即 18。