EOJ Monthly 2020.1

E. 数的变幻

单点时限: 1.0 sec

内存限制: 256 MB

Cuber QQ 正在刷 EOJ 上的水题,他正在做的一道题目是这样的。

给定一个正整数 $x$ :

  • 如果 $x$ 是奇数的话,则变幻成 $x-1$ ;
  • 如果 $x$ 是偶数的话,则变幻成 $\frac{x}{2}$ 。

如此往复地执行这个操作,直到 $x$ 变为 $1$ 。

显然这对于 Cuber QQ 来说过于简单了。于是 Cuber QQ 根据这个发明了一个序列,称为变幻序列, $x$ -变幻序列指的是,从 $x$ 作为变幻的开始,一直变幻到 $1$ 所构成的序列,例如 $7$ -变幻序列是 ${7,6,3,2,1}$ ; $10$ -变幻序列是 ${10,5,4,2,1}$ 。

而现在 Cuber QQ 在纸上写出了所有 $1$ 到 $n$ 变幻序列,他分别统计了每一个数在这些序列中出现的次数,例如当 $n=4$ 的时候,四个序列分别是 $[1]={1},[2]={2,1},[3]={3,2,1},[4]={4,2,1}$ ,则 数 $1$ 出现了 $4$ 次,数 $2$ 出现了 $3$ 次 ,数 $3$ 出现了 $1$ 次 ,数 $4$ 出现了 $1$ 次。

现在 Cuber QQ 想知道最大的数 $x$ 满足 $x$ 在所有 $1$ 到 $n$ 变幻序列中至少出现了 $k$ 次。

输入格式

第一行包含一个整数 $T(1\le T\le 10^4)$ ,表示数据组数。

对于每一组数据包含两个整数 $n,k(1\le k\le n\le 10^{18})$ ,含义如题面所述。

输出格式

对于每一组数据,输出一行一个整数表示答案。

样例

Input
4
4 1
4 2
4 3
4 4
Output
4
2
2
1