Bob has 2 types of sequences S₁ and S_2. They are defined as follows

S₁ = 1, 2, 3, 4, 5, 6...

S₂ = 1, -2, 3, -4, 5, -6...

Bob wants you to find the sum of the first N terms of the sequence.

Input Format

There T test cases, and the first line contains a single integer T.

The next T lines contains 2 integers each (type, N), denoting whether its S₁ or S₂, and the number N.

Constraints

1 $\leq$ T $\leq$ 10⁵

type is either 1 or 2

1 $\leq$ N $\leq$ 10⁹

Output Format

For each test case, output a new line, the required sum