The grasshopper is located on the numeric axis at the point with coordinate $x_0$.

Having nothing else to do he starts jumping between integer points on the axis. Making a jump from a point with coordinate $x$ with a distance $d$ to the left moves the grasshopper to a point with a coordinate $x - d$, while jumping to the right moves him to a point with a coordinate $x + d$.

The grasshopper is very fond of positive integers, so for each integer $i$ starting with $1$ the following holds: exactly $i$ minutes after the start he makes a jump with a distance of exactly $i$. So, in the first minutes he jumps by $1$, then by $2$, and so on.

The direction of a jump is determined as follows: if the point where the grasshopper was before the jump has an even coordinate, the grasshopper jumps to the left, otherwise he jumps to the right.

For example, if after $18$ consecutive jumps he arrives at the point with a coordinate $7$, he will jump by a distance of $19$ to the right, since $7$ is an odd number, and will end up at a point $7 + 19 = 26$. Since $26$ is an even number, the next jump the grasshopper will make to the left by a distance of $20$, and it will move him to the point $26 - 20 = 6$.

Find exactly which point the grasshopper will be at after exactly $n$ jumps.

The first line of input contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

Each of the following $t$ lines contains two integers $x_0$ ($-10^{14} \leq x_0 \leq 10^{14}$) and $n$ ($0 \leq n \leq 10^{14}$) — the coordinate of the grasshopper's initial position and the number of jumps.

Print exactly $t$ lines. On the $i$-th line print one integer — the answer to the $i$-th test case — the coordinate of the point the grasshopper will be at after making $n$ jumps from the point $x_0$.