题目描述

朱朱有一个无限长的升序数组 a={1,2,3,...}，即 ai=i。现在旭旭对 a 执行了 k次操作，具体来说：

• 每次操作，旭旭都会将数组的奇数下标的元素全部删除，只保留偶数下标的元素，同时剩余的元素如果左侧有空位就会左移，直到补满所有空位。 例如第一次操作后，a数组会从{1,2,3,...} 变为 {2,4,6,...}。

在所有操作执行完后，朱朱想知道 an 的值是多少，你的任务就是帮他求出所有 k 次操作执行完后 an 的值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤100) 代表数据组数，每组测试数据描述如下：

第一行两个整数 n,k(1≤n≤10e5,0≤k≤10)，分别表示询问的下标和操作的次数。

输出描述

对于每组测试数据： 在单独的一行输出一个整数表示所有操作执行完后 an的值。

Samples

2
4 1
3 0

8
3

Limitation

1s, 1024KiB for each test case.