题目描述

一只跳蚤，位于一根轴上的点$x_0$.

这只跳蚤喜欢到处乱跳，当它从x点向左跳d格后它会跳到点x-d，同理，当它从x点向右跳d格后它会跳到点x+d.

这只跳蚤很喜欢整数，所以它跳的时候也有规律：他将在第i次跳跃时跳i格。于是，第一次跳跃时他将从点1跳至点2，以此类推。

同时，如果跳蚤所在的点是偶数（如-4，0，2），它就往左跳；如果跳蚤所在的点是奇数（如-9，9），它就往右跳。

比如说：跳蚤跳了18次以后在点7，那么它下一次要跳19格，又由于7是奇数，所以往右跳，跳到点19+7=26处。接下来它要跳20格，由于26是偶数，所以往左跳，跳到点26-20=6处。

现在已知跳蚤的初始位置$x_0$和跳的次数n，求跳蚤最后将跳到哪一个点。

输入格式

这题有多组数据。

第一行输入一个整数t（1$\leqslant$t$\leqslant$10^14），代表共有t组数据。

接下去t行，每行一个$x_0$和一个n，含义见题目描述。-10^14\leqslant$$x_0$$\leqslant10^14,0$\leqslant$n$\leqslant$10^14

输出格式

t行，每一行一个数，代表其对应一行的跳蚤最终的位置。