[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$