题目背景

就是这样，Madeline。

保持呼吸。你能行。

题目描述

“你的呼吸让那片羽毛一直飘着。”

“平稳缓慢地呼吸，吸气，吐气。”

“看吧，每次都是这么轻松。”

随着 Madeline 的呼吸，羽毛上下移动着。

通过 Madeline 的观察，她还发现，羽毛似乎遵循这一种神奇的运动轨迹。

在每一轮呼吸中，羽毛会在特定的地方停止，这些地方都是有魔力的，具体来说，第 $i$ 个停留处的魔力是 $(i+1)^2-1$。

并且，在一轮呼吸停止时，羽毛会渗透出一些能量，只要能用这些能量沟通这些停止的地方，Madeline 就能运用羽毛的力量飞翔。更具体的，由于同性相斥，两个地方魔力的相似程度越高就越难被沟通，沟通两个地方所需要的能量为这两个地方魔力的 $gcd$。

在一轮一轮的呼吸中，Madeline 已经无暇算出最少需要的能量，由于羽毛渗透出的能量不多，你能帮帮她算出最少需要多少能量来沟通这些羽毛停止的地方吗？

输入格式

第一行一个正整数 $T$，表示呼吸轮数。

接下来 $T$ 行一行一个正整数 $n$，表示该轮呼吸中羽毛停止的地方个数。

输出格式

输出 $T$ 行，一行一个整数，最少需要的能量。

4
1
2
3
9

0
1
2
8

提示

n=3 的样例解释如下图

对于 $5\%$ 的数据，$n \leq 3$

对于 $10\%$ 的数据，$n \leq 1000$

对于 $50\%$ 的数据，$n \leq 10^6$,$T \leq 10$

对于 $100\%$ 的数据，$n \leq 10^{18}$,$T \leq 100$