Migrated from Lutece 3245 瑠璃の鳥

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

哽咽了一下，调整着呼吸 。冬子，让我看看你的画吧。

翻开了画布。

是一只鸟儿，是一只刚刚破卵而出展翅而飞的雏鸟。

画的名字《琉璃之鸟》写在了这幅画的角落。

破壳而出奔向天际的琉璃色鸟儿——

......终于打破了壳，变得自由了呢，冬子——

朽木冬子给时坂玲人提了新的委托，这次的委托形式如下：

定义一个正整数 $x$ 是 good number ，当且仅当存在 $a,b\in \mathbb{N^+},a<b$，且 $x=b^2-a^2$。

现在冬子想要知道，将所有的 good number 升序排序后，第 $k$ 个 good number 是什么。

Input

输入的第一行包括一个正整数 $t$，表示冬子进行了 $t$ 次询问。

接下来的 $t$ 行每行一个正整数 $k$，表示询问第 $k$ 小的 good number 的值。

Output

输出 $t$ 行每行一个正整数表示答案。

Samples

3
1
2
3

3
5
7

Constraints

$1\le t\le 10^5,1\le k\le 10^9$

Note

样例解释：因为 $3=2^2-1^2,5=3^2-2^2,7=4^2-3^2$，因此 $3,5,7$ 都是 good number。