题目背景

梅莉这个学期选修了经济学。但是主修心理学的她实在不擅长经济领域的分析，为此她时常抱怨自己学不会，想退课。

但是如果现在退掉的话这学期的学分就不够啦，因此她根据“梦中”的经历，“胡诌”了一个简单到不现实的市场模型，并依据这个模型编起了 essay。为了方便地编出图表，她需要写一个程序来查询每个时刻的市场贸易差。

题目描述

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

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

输入格式

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

输出格式

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

9
1
10
100
1000
10000
100000
1000000
10000000
100000000

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

提示

对于所有数据，$1 \leq q \leq 10^5$，$1 \leq k \leq 4\times 10^{18}$。