Calculate the Sum If You Can

Limits 2s, 512 MB

This problem deals with the following expression:

12+12+12+12+12+12+12+...1-2+1-2+1-2+1-2+1-2+1-2+1-2+...

Given nn, you have to determine the sum of the expression up to the nn-th term.

Input

The first line of input contains the number of test cases TT (1T1000001 ≤ T ≤ 100000). The next TT lines each contains an integer nn (0n10120 ≤ n ≤ 10^{12}).

Output

For each case find the sum up to nn-th term of the given series.

Sample

InputOutput
3
1
2
5
1
-1
-1