{"raw_statement":[{"iden":"statement","content":"小 J 家门前有两棵树，一棵是二叉树，一棵是三叉树。\n\n你被小 J 叫来修剪他的二叉树，使得他的二叉树的“美丽值”最大，所谓一棵树的美丽值 $=$ 这棵树的点的编号之和 $\\div$ 这棵树的深度（结果向下取整）。\n\n这棵二叉树有一个构建参数 $n$，构建方式如下：\n\n```cpp\nvoid build(int s,int t,int p){\n  if(s==t) return ;\n  build(s,(s+t)/2,2*p);\n  build((s+t)/2+1,t,2*p+1);\n  add_edge(p,2*p),add_edge(p,2*p+1);\n}\n\nint main(){\n  build(1,n,1);\n  return 0;\n}\n```\n\n其中 `build(s,t,p)` 函数参数中的 $p$ 是当前点的编号，`add_edge(x,y)` 函数是指将编号为 $x$ 的点向编号为 $y$ 的点连接一条有向边。\n\n容易发现这棵树的根节点是 $1$，并且我们规定节点的深度为节点到根节点路径上经过的点的个数（包括自己和根节点），这棵树的深度即为所有节点深度的最大值。\n\n对于 $n=3$ 的情况，最后构建出来的结果如下，这棵树的深度为 $3$，你需要选择一个深度 $k$ 把深度大于 $k$ 的点都剪掉，但是 $k$ 必须**大于等于** $1$ 且**小于等于**这棵树的深度。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ueggbyn8.png)\n\n小 J 还给了你一个要求，你剪去的节点个数一定得大于等于 $m$ 他才会高兴，你需要保证让他高兴的同时树的“美丽值”最大。\n\n现在小 J 给了你构建树的参数 $n$ 和至少剪的节点个数 $m$，要你求出来他的树在你修剪后最大的美丽值是多少，如果无论如何你也不可能让小 J 高兴，输出 $-1$。"},{"iden":"input","content":"本题有多组数据。\n\n第一行一个正整数 $T$，表示数据组数。\n\n对于每组数据：\n\n输入共一行两个整数 $n,m$，表示构建二叉树的参数和你至少剪掉的节点个数。"},{"iden":"output","content":"对于每组数据：输出一行一个整数，表示能够获得的最大的“美丽值”，如果无法让小 J 高兴，输出 $-1$。"},{"iden":"note","content":"#### 【样例解释 #1】\n\n对于第一组样例，$n$ 都等于 $3$，构建出来的树同题面所示。\n\n如果我们选择把深度大于 $1$ 的节点全部剪掉，那么我们剪掉了 $2,3,4,5$ 共 $4$ 个节点，美丽值为 $1$。\n\n如果我们选择把深度大于 $2$ 的节点全部剪掉，那么我们剪掉了 $4,5$ 共 $2$ 个节点，美丽值为 $\\lfloor \\dfrac{1+2+3}{2}\\rfloor = 3$。\n\n如果我们选择把深度大于 $3$ 的节点全部剪掉，那么我们没有剪掉任何节点，美丽值为 $\\lfloor \\dfrac{1+2+3+4+5}{3}\\rfloor = 5$。\n\n所以对于 $m=0$ 的情况，答案为 $5$；对于 $1 \\le m \\le 2$ 的情况，答案为 $3$；对于 $3 \\le m \\le 4$ 的情况，答案为 $1$；其它情况，无解输出 $-1$。\n\n#### 【数据范围】\n\n对于所有测试数据，满足 $1 \\le T \\le 10^5$，$1 \\le n \\le 10^9$，$0 \\le m \\le 2 \\times 10^9$。\n\n**本题开启捆绑测试，所有数据范围均相同的测试点捆绑为一个 $\\text{Subtask}$。**\n\n各测试点的附加限制如下表所示。\n\n| 测试点 | $n \\le$ | $m \\le$ | $T \\le$ | 特殊限制 |\n| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |\n| $1 \\sim 2$ | $10^3$ | $10^5$ | $10^3$ | 无 |\n| $3 \\sim 4$ | $10^6$ | $2 \\times 10^6$ | $10^5$ | 无 |\n| $5$ | $10^9$ | $1$ | $10^5$ | 无 |\n| $6$ | $10^9$ | $2$ | $10^5$ | 无 |\n| $7 \\sim 8$ | $10^9$ | $3$ | $10^5$ | 无 |\n| $9 \\sim 10$ | $10^9$ | $2 \\times 10^9$ | $10^5$ | $m \\ge 1$ |\n| $11 \\sim 12$ | $10^9$ | $10^3$ | $10^5$ | 无 |\n| $13 \\sim 16$ | $10^9$ | $2 \\times 10^9$ | $10$ | 无 |\n| $17 \\sim 20$ | $10^9$ | $2 \\times 10^9$ | $10^5$ | 所有 $n$ 均相同 |\n| $21 \\sim 25$ | $10^9$ | $2 \\times 10^9$ | $10^5$ | 无 |"}],"translated_statement":null,"sample_group":[["6\n3 0\n3 1\n3 2\n3 3\n3 4\n3 5","5\n3\n3\n1\n1\n-1"],["10\n5 5\n10 0\n999 155\n135 92\n1000232 234255\n10293845 1239485\n123948 1239454\n12394 2131094\n1000000000 98765432\n1000000000 999999999","3\n40\n52377\n1161\n27487764480\n5864061665280\n-1\n-1\n19215358392218419\n4969489234738635"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}