题目

《只狼：影逝二度》是一款由FromSotfware开发的动作冒险游戏 , 在游戏中玩家扮演一名战国时期的忍者 "狼", 试图向袭击他并绑架了他的领主的武士家族复仇。

作为一款由宫崎老贼指导的游戏 , 采用非常严厉的死亡惩罚机制 , 如果玩家在携带a的钱时死亡 , 那么玩家的钱将会变为$\pmb{ \lceil \frac{a}{2}\rceil}$,$\pmb{ \lceil \frac{a}{2}\rceil}$表示对$\pmb{ \frac{a}{2}}$进行 向上取整。

二次元学长最近沉迷于这款游戏 , 为了达成修罗结局 , 他不得不杀了永真小姐姐 , 作为手残党的他连续死亡了k次才杀死了永真 , 并且在这k次死亡中 , 他没有收集或花费任何钱。 二次元初始身上携带了m 的钱 , 在成功击败永真后，他想知道自己还剩下多少钱。由于战斗时间太长二次元累的动弹不得，请你帮他计算还剩余多少钱。

输入

有多个测试样例 , 输入的第一行包含一个整数T ($\pmb{0\le T\le10^3}$)，表示测试用例的数量。对于每个测试用例：第一行也是唯一一行 , 包含两个整数m和k(($\pmb{0\le m\le10^9}$,$\pmb{1\le k\le10^9}$)) , 表示二次元刚开始身上的钱的数量以及连续死亡的次数。

输出

每个测试用例输出一行 , 每行包含一个整数 , 表示k次死亡后剩下的钱数。

样例

4
10 1
7  1
10 2
7  2

5
4
3
2

样例解释

在第三个示例测试用例中 , 当二次元第一次死亡时 , 他身上的钱会从 10 减少到 5 , 当他第二次死亡时 , 他身上的钱会从 5 减少到 3。