Calculate the Sum If You Can

This problem deals with the following expression:

$1-2+1-2+1-2+1-2+1-2+1-2+1-2+...$

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

Input

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

Output

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

Sample

Input	Output
3 1 2 5	1 -1 -1