解题思路

设

把每个质因子幂

题目内容

给定一个正整数 $x$。请在所有满足 $lcm(a,b,c)=x$ 的正整数三元组 $(a,b,c)$ 中，找到使 $a+b+c$ 最小的一组，并输出这个最小值 $a+b+c$。

其中最小公倍数 $lcm(a,b,c)$ 定义为能被 $a,b,c$ 同时整除的最小正整数。例如：

$lcm(2,3,4)=12；lcm(5,5,10)=10$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T（1≤T≤2×10^5）$代表数据组数，每组测试数据描述如下：

每组输入一个正整数 $x（1≤x≤10^7）$。

输出描述

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

样例1

输入

4
1
6
12
30

输出

3
6
8
10

说明

当 $x=1$ 时，取 $(1,1,1)$，和为 $3$。

当 $x=6$ 时，取 $(1,2,3)$，和为 $6$。

当 $x=12$ 时，取 $(1,3,4)$，和为 $8$。

当 $x=30$ 时，取 $(2,3,5)$，和为 $10$。