# Half Measures

National Girls' Programmi...
Limits 4s, 512 MB

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

InputOutput
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$.