[Celeste-B] Golden Feather
题目背景
> 就是这样,Madeline。
> 保持呼吸。你能行。
题目描述
“你的呼吸让那片羽毛一直飘着。”
“平稳缓慢地呼吸,吸气,吐气。”
“看吧,每次都是这么轻松。”
随着 Madeline 的呼吸,羽毛上下移动着。
通过 Madeline 的观察,她还发现,羽毛似乎遵循这一种神奇的运动轨迹。
在每一轮呼吸中,羽毛会在特定的地方停止,这些地方都是有魔力的,具体来说,第 $i$ 个停留处的魔力是 $(i+1)^2-1$。
并且,在一轮呼吸停止时,羽毛会渗透出一些能量,只要能用这些能量沟通这些停止的地方,Madeline 就能运用羽毛的力量飞翔。更具体的,由于同性相斥,两个地方魔力的相似程度越高就越难被沟通,沟通两个地方所需要的能量为这两个地方魔力的 $gcd$。
在一轮一轮的呼吸中,Madeline 已经无暇算出最少需要的能量,由于羽毛渗透出的能量不多,你能帮帮她算出最少需要多少能量来沟通这些羽毛停止的地方吗?
输入输出格式
输入格式
第一行一个正整数 $T$,表示呼吸轮数。
接下来 $T$ 行一行一个正整数 $n$,表示该轮呼吸中羽毛停止的地方个数。
输出格式
输出 $T$ 行,一行一个整数,最少需要的能量。
输入输出样例
输入样例 #1
4
1
2
3
9
输出样例 #1
0
1
2
8
说明
n=3 的样例解释如下图
![T1_2.png](https://i.loli.net/2019/09/14/PtflkNCE8b3iKzB.png)
![T1.png](https://i.loli.net/2019/09/14/AIYlMZgonL7thfu.png)
对于 $5\%$ 的数据,$n \leq 3$
对于 $10\%$ 的数据,$n \leq 1000$
对于 $50\%$ 的数据,$n \leq 10^6$,$T \leq 10$
对于 $100\%$ 的数据,$n \leq 10^{18}$,$T \leq 100$