Write out the consecutive digits $$1, 2, 3, \ldots, n$$ and then alternately place the operators + (sum) and - (subtraction) between each two consecutive digits. Which number do you obtain when you calculate this series? In case of $$n = 12$$ we get: \[+1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 1 + 0 - 1 + 1 - 1 + 2 = 5\]

Input

The input consists of $$t$$ test cases ($$t \leq 100$$). The first line of the input contains an integer $$t$$. Then $$t$$ lines follow, describing the various test cases. Each case is described by the integer $$n$$ ($$1 \leq n ? 10^{15}$$).

Output

For every $$n$$ from the input, print the value of the alternating sum to a separate line.

Example

Input:

3
12
83
182

Output:

5
14
6