Half Measures

The numbers $1,2,3, \cdots n$ (each integer from $1$ to $n$ once) are written on a board. In one operation, Jesse can choose any number $x$ from the board and replace it by $\lfloor \frac{x}{2} \rfloor$(Half of $x$ rounded down). Jesse wants to minimize the sum of the integers after performing exactly $k$ operations. Help Jesse.

Input

The first line contains $T (1 \leq T \leq 10^5)$, the number of testcases.

Each of the following $T$ lines contain two space separated integers, $n$ and $k$$(1 \leq n, k \leq 10^9)$.

Output

For each testcase, print a single line containing a single integer, the minimum sum after performing exactly $k$ operations.

Sample

Input	Output
3 4 1 4 3 3 10	8 5 0
For the first case, $1, 2, 3, 4$ are written. Jesse picks $x = 3$ and replaces it by $\lfloor \frac{3}{2} \rfloor = 1$. Now the board contains $1, 2, 1, 4$ with sum $8$. For the second case, initially the board contains $1, 2, 3, 4$. For the first operation, Jesse chooses $x = 1$, replaces it by $0$. The board contains $0, 2, 3, 4$. For the second operation, Jesse chooses $x = 4$, replaces it by $2$. The board contains $0, 2, 3, 2$. For the third operation, Jesse chooses $x = 3$, replaces it by $1$. The board contains $0, 2, 1, 2$. For the third case, Jesse can make everything $0$.