形式化题意：

给定 $m$，求任意一个 $n$ 满足：

$$ \sum_{i=1}^n i[\gcd(i,n) = 1] = m $$

输入格式

第一行一个 $t$ 表示数据组数。

接下来 $t$ 行一行一个正整数 $m$ 表示小 Z 告诉小 Y 的数。

输出格式

对于每组测试数据，输出一个 $n$ 表示小 Z 拥有的数。

问题保证至少有一个解。如果解不唯一，输出任意一个 $n$ 均可。

对于所有测试点 $2 \leq m \leq 10^{36},1 \leq t \leq 200$。

对于前 10% 的测试点，保证 $n ≤ 400$。

对于前 30% 的测试点，$m \leq 10^9$。

对于前 50% 的测试点，$m \leq 10^{18}$。

对于另外 10% 的测试点，保证 $n$ 一定是质数。