Migrated from Lutece 3256 SKP Wants to Have a QHJ Bucket

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

SKP 同学的梦想，除了成为魔法少女外，还有一个是，把周一、周二、周三、周四、周五、周六、周日，全部变为疯狂星期四。

但是她最近有点揭不开锅了，她已经吃了一周的番茄鸡蛋面了，现在十分想要吃一次炸鸡。这时候我们的大善人 QHJ 店长找到了她，并给她说，如果她能够解决 QHJ 店长提出的一个问题，她就能白嫖一次 QHJ 全家桶。

具体的，QHJ 的问题是：给出一个正整数 $c\;(1\le c\le 10^{12})$，求 $a,b\in N_+\;\textrm{s.t.}\;ab^2=c$ 且 $a+2b$ 的值最大。

这可难住了我们的 SKP 同学，你能帮帮她解决这个问题吗？

Input

输入数据的第一行为一个整数 $T\;(1\le T\le 10^3)$，表示有 $T$ 组测试数据。

接下来的 $T$ 行，每行一个整数 $c$，含义如题面所示。

Output

对于每一组测试数据，输出一行一个整数，表示在满足 $ab^2=c$ 的限制下 $a+2b$ 的最大值。

Samples

2
1
4

3
6

Constraints

$1\le T\le 10^3$

$1\le c\le 10^{12}$