(应sanchi强烈要求，给蟑螂出题)

我是一只蟑螂，为了改变人们对蟑螂的刻板印象，我决心展开一场文化输出运动。为了实现这个目标，我深知自己需要足够的资金支持。于是，我每天半夜都会偷偷地打开房间主人的电脑，研究市场经济模型，希望能从中找到赚钱的方法，为“蟑螂刻板印象改变计划”赚取第一桶金。

在夜深人静的时候，我小心翼翼地从房间的角落爬出来，尽量不发出一点声响。我熟悉这间房子的每一个角落，知道哪里最安全，哪里最容易找到食物。我熟练地钻进电脑桌的缝隙，来到了电脑面前。

人类的电脑对我来说简直就是一个神秘的宝藏。这里有数不清的信息，关于经济、历史、文化、科技，应有尽有。我如饥似渴地阅读着每一篇文章，试图从中找到赚钱的方法。

经过一段时间的研究，我终于发现了一个潜在的赚钱机会：炒股。炒股是一种高收益、高风险的投资方式，对人类的经济知识要求很高。但对我来说，这不成问题。作为一名蟑螂，我可以快速地处理大量信息，轻松地解读股市走势。

于是，我开始学习炒股的技巧。我每天都会阅读大量的股票分析报告，了解市场的动态，预测股票价格的走势。随着时间的流逝，我对炒股越来越熟练，成功的概率也越来越高。

但是，我很快就遇到了一个难题，在学习市场经济的时候，我遇到了一个奇怪的市场模型，为了了解这个市场模型从而是我从中获利，我就必须随时知道每个时刻的市场贸易差，但是我只是一只蟑螂，这对我来说太难了，于是我只好求助那个神秘的东方学校，南阳理工 · 霍格沃兹 分校，希望能获得acm预备役队员们的相助，我将问题简化发送给了他们，请求支援！！！只有他们才可以做出这道题，只有他们可以拯救我们这个物种！！

我坚信，我一定能够实现“蟑螂刻板印象改变计划”的目标。总有一天，我们蟑螂会像一个受人尊敬的物种，和平地与人类共同生活在这个星球上。

信封内容如下

亲爱的展博，当你看到这封信的时候，我已经在去机场的路上了。请原谅我改签了航班，我知道，如果我看到你们，肯定就走不了了。因为我舍不得你们每个人，尤

亲爱的acm队员，我知道你们每个人都有这沉鱼落雁之容，闭月羞花之貌；赛过西施，比过貂蝉，胜过昭君，气死玉环；纤腰婀娜，玉腿修长，在这个软件acm招新赛偏偏起舞，舞起来是花蝴蝶，停下来是蝴蝶花。 用花来形容，那就是玉簪碗乌云乌春卷盘龙，墨跟扎条红绒花的绳，桂花油茶青丝墨，菊花的色，压鬓的金花黄橙橙，柳叶花的弯眉弯又细，葡萄画的眼镜水灵灵，玄灵花的样，樱桃花的嘴，玉米花的银牙口中盛，元宝花的耳朵，灯笼花的坠，丁香花的排环耀眼明，伸胳膊就像是白莲花的藕，十指尖尖像没有花的葱，坐下好似骑一匹桃红花的马，秀荣花的大刀单手琴。

所以我希望你们可以帮我解决一个问题:

市场每一天的贸易差可以视为一个有周期性规律的数列 $a$ ：[0] , [0,1,0,−1,0] , [0,1,2,1,0,−1,−2,−1,0] , [0,1,2,3,2,1,0,−1,−2,−3,−2,−1,0] … 具体而言，$a$ 可以被分为无穷段，第 $i$ 段的内容为 {0,1,⋯ ,$i$ , $i$ −1,⋯ ,0,−1,⋯ ,− $i$ , $-i$ +1,⋯ 0}。如下图所示，是将 $a$ 数列内的前一些点绘制在坐标轴上的情况：

现在蟑螂对市场发起了 $q$ 次询问，每次她会给定一个 $k$，希望求出 $a_k$ 是多少。

Format

Input

• 第一行有一个正整数 $q$，表示询问次数。
• 接下来 $q$ 行，每行一个正整数 $k$，描述每次询问。

输出格式

Output

• 输出共 $q$ 行。对于每次询问，输出对应的结果。

Samples

9
1
10
100
1000
10000
100000
1000000
10000000
100000000

0
1
6
-9
-11
-128
406
1629
5154

Limitation

对于所有数据，1≤ $q$ ≤$10^5$, 1≤ $k$ ≤4×$10^{18}$。

1s, 1024KiB for each test case.