PROG0027 - Alternating sum

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

Schrijf achtereenvolgens de getallen $1, 2, 3, \ldots, n$ uit, en plaats daarna afwisselend de operatoren + (optelling) en - (aftrekking) tussen elke twee opeenvolgende cijfers. Wat is het getal dat je bekomt als je deze uitdrukking uitrekent? Voor $n = 12$ krijgen we bijvoorbeeld: $$+1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 1 + 0 - 1 + 1 - 1 + 2 = 5$$

Invoer

De invoer bestaat uit $t$ testgevallen ($t \leq 100$). De eerste regel van de invoer bevat een natuurlijk getal $t$. Daarna volgen $t$ regels die de verschillende testgevallen omschrijven. Elk geval wordt omschreven door een natuurlijk getal $n$ ($1 \leq n ? 10^{15}$).

Uitvoer

Schrijf voor elk getal $n$ uit de invoer, de waarde van de alternerende som naar een afzonderlijke regel.

Voorbeeld

Invoer:

3
12 83 182

Uitvoer:

5
14
6

Added by:Peter Dawyndt
Date:2011-07-19
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.