Market Trade Difference Sequence

The market trade difference sequence a is defined by an infinite number of segments. The first few segments are illustrated as follows:

• Segment 0: \( [0] \)
• Segment 1: \( [0,1,0,-1,0] \)
• Segment 2: \( [0,1,2,1,0,-1,-2,-1,0] \)
• Segment 3: \( [0,1,2,3,2,1,0,-1,-2,-3,-2,-1,0] \)

In general, for any segment \( i \) (with \( i\ge0 \)), the segment is defined as:

[ S_i = { 0,1,2,\dots,i,, i-1,\dots,0,, -1,\dots,-i,, -i+1,\dots,0 } ]

The overall sequence a is the concatenation of all segments in order. Given a 0-indexed position \( k \), your task is to determine \( a_k \).

inputFormat

The first line contains an integer \( q \) representing the number of queries. Each of the following \( q \) lines contains a non-negative integer \( k \).

It is guaranteed that the input values are valid.

outputFormat

For each query, output a single integer \( a_k \) in a separate line.

sample

6
0
1
2
5
6
14

0
0
1
0
0
0