Background

Mellie took an economics elective this semester. However, since her major is psychology, she is really not good at analyzing economics. Because of this, she often complains that she cannot learn it and wants to drop the course.

But if she drops it now, she will not have enough credits this semester. So, based on what she “experienced in a dream,” she “made up” a market model that is simple to the point of being unrealistic, and wrote an essay using this model. To make it easier to create charts, she needs to write a program to query the market trade balance at each moment.

Problem Description

The daily trade balance in the market can be seen as a periodic sequence $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$.

More specifically, $a$ can be divided into infinitely many segments. The content of the $i$-th segment is $\{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\}$. The figure below shows the plot of some of the first points in sequence $a$ on the coordinate axes:

Now Mellie makes $q$ queries to the market. Each time, she is given an integer $k$ and wants to find the value of $a_k$.

Input Format

• The first line contains a positive integer $q$, which represents the number of queries.
• The next $q$ lines each contain a positive integer $k$, describing each query.

Output Format

• Output a total of $q$ lines. For each query, output the corresponding result.

9
1
10
100
1000
10000
100000
1000000
10000000
100000000

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

Hint

Constraints: for all testdata, $1 \leq q \leq 10^5$, $1 \leq k \leq 4\times 10^{18}$.

Translated by ChatGPT 5