《只狼：影逝二度》（Sekiro: Shadows Die Twice）是由 FromSoftware 开发、Activision 发行的一款动作冒险电子游戏。在游戏中，玩家扮演战国时代的忍者“狼”，试图向袭击他并绑架其主公的武士家族复仇。

由宫崎英高执导的《只狼》不出所料地拥有非常严苛的死亡惩罚。如果玩家在携带 $g$ 金钱时死亡，金钱数额将减少至 $\lceil \frac{g}{2} \rceil$，其中 $\lceil \frac{g}{2} \rceil$ 表示满足 $2g' \ge g$ 的最小整数 $g'$。

作为一名游戏新手，BaoBao 在游戏中连续死亡了 $k$ 次。已知 BaoBao 在第一次死亡前携带了 $n$ 金钱，且在 $k$ 次死亡期间没有收集或花费任何金钱，请问在 $k$ 次死亡后他剩余多少金钱？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（约 $10^3$），表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$ ($0 \le n \le 10^9, 1 \le k \le 10^9$)，分别表示 BaoBao 初始携带的金钱数和死亡次数。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示 $k$ 次死亡后剩余的金钱数。

样例

输入格式 1

4
10 1
7 1
10 2
7 2

输出格式 1

5
4
3
2

说明

对于第三组样例，当 BaoBao 第一次死亡时，他携带的金钱从 10 减少到 5；当他第二次死亡时，他携带的金钱从 5 减少到 3。