Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 4125
Sekiro

Time Limit: 1 Second      Memory Limit: 65536 KB

Sekiro: Shadows Die Twice is an action-adventure video game developed by FromSoftware and published by Activision. In the game, the players act as a Sengoku period shinobi known as Wolf as he attempts to take revenge on a samurai clan who attacked him and kidnapped his lord. As a game directed by Hidetaka Miyazaki, Sekiro (unsurprisingly) features a very harsh death punishment. If the player dies when carrying $g$ amount of money, the amount of money will be reduced to $\left\lceil \frac{g}{2} \right\rceil$, where $\left\lceil \frac{g}{2} \right\rceil$ indicates the smallest integer $g'$ that $2g' \ge g$.

As a noobie of the game, BaoBao has died $k$ times in the game continuously. Given that BaoBao carried $n$ amount of money before his first death, and that BaoBao didn't collect or spend any money during these $k$ deaths, what's the amount of money left after his $k$ deaths?

#### Input

There are multiple test cases. The first line of the input contains an integer $T$ (about $10^3$), indicating the number of test cases. For each test case:

The first and only line contains two integers $n$ and $k$ ($0 \le n \le 10^9$, $1 \le k \le 10^9$), indicating the initial amount of money BaoBao carries and the number of times BaoBao dies in the game.

#### Output

For each test case output one line containing one integer, indicating the amount of money left after $k$ deaths.

#### Sample Input

4
10 1
7 1
10 2
7 2


#### Sample Output

5
4
3
2


#### Hint

For the third sample test case, when BaoBao dies for the first time, the money he carries will be reduced from 10 to 5; When he dies for the second time, the money he carries will be reduced from 5 to 3.

Author: WENG, Caizhi
Source: The 10th Shandong Provincial Collegiate Programming Contest
Submit    Status