说明

你有一个数字 $x$。已知有一个数 $y$ 在二进制下恰有 $k$ 位为 $1$，给定 $k$，你需要求出所有可能的 $y$ 与 $x$ 的差的绝对值最小是多少。

输入格式

本题包含多组测试数据。

第一行输入一个整数 $T$，表示数据组数。

接下来 $T$ 行，每行输入两个整数 $x$ 和 $k$，含义如上文所述。

输出格式

对于每组测试数据，输出一行一个整数，表示在二进制下恰有 $k$ 位为 $1$ 的数与 $x$ 的差的绝对值最小是多少。

2
6 3
7 4

1
8

提示

样例解释

对于第一组询问，可以选择 $y=7=(111)_2$，与 $x=6$ 仅相差 $1$。可以证明 $1$ 是最小的可能的差。

数据范围

对于 $100\%$ 的数据，$1\le T \le 15$，$1\le x \le 2^{60}$，$1\le k \le 60$。