题目描述

小 J 家门前有两棵树，一棵是二叉树，一棵是三叉树。

你被小 J 叫来修剪他的二叉树，使得他的二叉树的“美丽值”最大，所谓一棵树的美丽值 $=$ 这棵树的点的编号之和 $\div$ 这棵树的深度（结果向下取整）。

这棵二叉树有一个构建参数 $n$，构建方式如下：

void build(int s,int t,int p){
  if(s==t) return ;
  build(s,(s+t)/2,2*p);
  build((s+t)/2+1,t,2*p+1);
  add_edge(p,2*p),add_edge(p,2*p+1);
}

int main(){
  build(1,n,1);
  return 0;
}

其中 build(s,t,p) 函数参数中的 $p$ 是当前点的编号，add_edge(x,y) 函数是指将编号为 $x$ 的点向编号为 $y$ 的点连接一条有向边。

容易发现这棵树的根节点是 $1$，并且我们规定节点的深度为节点到根节点路径上经过的点的个数（包括自己和根节点），这棵树的深度即为所有节点深度的最大值。

对于 $n=3$ 的情况，最后构建出来的结果如下，这棵树的深度为 $3$，你需要选择一个深度 $k$ 把深度大于 $k$ 的点都剪掉，但是 $k$ 必须大于等于 $1$ 且小于等于这棵树的深度。

小 J 还给了你一个要求，你剪去的节点个数一定得大于等于 $m$ 他才会高兴，你需要保证让他高兴的同时树的“美丽值”最大。

现在小 J 给了你构建树的参数 $n$ 和至少剪的节点个数 $m$，要你求出来他的树在你修剪后最大的美丽值是多少，如果无论如何你也不可能让小 J 高兴，输出 $-1$。

输入格式

本题有多组数据。

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

对于每组数据：

输入共一行两个整数 $n,m$，表示构建二叉树的参数和你至少剪掉的节点个数。

输出格式

对于每组数据：输出一行一个整数，表示能够获得的最大的“美丽值”，如果无法让小 J 高兴，输出 $-1$。

6
3 0
3 1
3 2
3 3
3 4
3 5

5
3
3
1
1
-1

10
5 5
10 0
999 155
135 92
1000232 234255
10293845 1239485
123948 1239454
12394 2131094
1000000000 98765432
1000000000 999999999

3
40
52377
1161
27487764480
5864061665280
-1
-1
19215358392218419
4969489234738635

提示

【样例解释 #1】

对于第一组样例，$n$ 都等于 $3$，构建出来的树同题面所示。

如果我们选择把深度大于 $1$ 的节点全部剪掉，那么我们剪掉了 $2,3,4,5$ 共 $4$ 个节点，美丽值为 $1$。

如果我们选择把深度大于 $2$ 的节点全部剪掉，那么我们剪掉了 $4,5$ 共 $2$ 个节点，美丽值为 $\lfloor \dfrac{1+2+3}{2}\rfloor = 3$。

如果我们选择把深度大于 $3$ 的节点全部剪掉，那么我们没有剪掉任何节点，美丽值为 $\lfloor \dfrac{1+2+3+4+5}{3}\rfloor = 5$。

所以对于 $m=0$ 的情况，答案为 $5$；对于 $1 \le m \le 2$ 的情况，答案为 $3$；对于 $3 \le m \le 4$ 的情况，答案为 $1$；其它情况，无解输出 $-1$。

【数据范围】

对于所有测试数据，满足 $1 \le T \le 10^5$，$1 \le n \le 10^9$，$0 \le m \le 2 \times 10^9$。

本题开启捆绑测试，所有数据范围均相同的测试点捆绑为一个 $\text{Subtask}$。

各测试点的附加限制如下表所示。

测试点	$n \le$	$m \le$	$T \le$	特殊限制
$1 \sim 2$	$10^3$	$10^5$	$10^3$	无
$3 \sim 4$	$10^6$	$2 \times 10^6$	$10^5$
$5$	$10^9$	$1$
$6$		$2$
$7 \sim 8$		$3$
$9 \sim 10$		$2 \times 10^9$		$m \ge 1$
$11 \sim 12$		$10^3$		无
$13 \sim 16$		$2 \times 10^9$	$10$
$17 \sim 20$			$10^5$	所有 $n$ 均相同
$21 \sim 25$				无