Chef is playing a game on the non-negative x-axis. It takes him $1$ second to reach from $i^{th}$ position to $(i-1)^{th}$ position or $(i+1)^{th}$ position. The chef never goes to the negative x-axis. Also, Chef doesn't stop at any moment of time.

The movement of chef can be described as follows.
At the start he is standing at $x=0$ at time $0$.
In the first round, he moves towards $x=1$ and comes back to the $x=0$ position.
In the second round, he moves towards the $x=2$ and comes back again to $x=0$.
Generalizing, in the $k^{th}$ round, he moves from $x=0$ to $x=k$ and then returns back to $x=0$ at the end of the round. This goes on as the game progresses.

For Example, the path of Chef for $3^{rd}$ round is given below.
$0 - 1 - 2 - 3 - 2 - 1 - 0$

The overall path followed by Chef would look somewhat like this:
$0 - 1 - 0 - 1 - 2 - 1 - 0 - 1 - 2 - 3 - 2 - 1 - 0 - 1 - 2 - 3 - 4 - 3 - …$

You are given two non-negative integers $N$ and $K$. You have to tell the time at which Chef arrives at $x=N$ for the $K^{th}$ time.

Note - Chef can not skip a position while visiting the positions.

------ Input: ------
The first line contains $T$ the number of test cases. Then the test cases follow.
Each test case contains a single line of two integers $N$ and $K$.

------ Output: ------
For each test case, print a single line containing one integer -- the time taken by the chef to arrive at $x=N$ for the $K^{th}$ time by modulo $1,000,000,007$.

------ Constraints ------
$1 ≤ T ≤ 10^{5}$
$0 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------
5
0 1
1 1
2 1
1 3
4 6
----- Sample Output 1 ------
0
1
4
5
46
----- explanation 1 ------
Test Case 1:
Chef starts the journey from the $N = 0$ at time $t = 0$ and it's the first time $(K = 1)$, he is here. So, the answer is $0$.

Test Case 2:
Chef starts the journey from the $N = 0$ at time $t = 0$ then goes to $N = 1$ at $t = 1$ and it's the first time $(K = 1)$, he is here. So, the answer is $1$.

Test Case 4:
The path followed by Chef to reach $1$ for the third time is given below.
$0 - 1 - 0 - 1 - 2 - 1$
He reaches $1$ for the third time at $t=5$.

见题面

见题面