Problem Description

There are two trees in front of Xiao J’s house: one is a binary tree, and the other is a ternary tree.

You are asked by Xiao J to prune his binary tree so that its “beauty value” is as large as possible. The beauty value of a tree $=$ (the sum of the node labels in the tree) $\div$ (the depth of the tree), rounded down.

This binary tree has a construction parameter $n$, and it is built as follows:

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;
}

In the function parameters of build(s,t,p), $p$ is the label of the current node. The function add_edge(x,y) means adding a directed edge from the node labeled $x$ to the node labeled $y$.

It is easy to see that the root node of this tree is $1$. We define the depth of a node as the number of nodes on the path from it to the root (including itself and the root). The depth of the tree is the maximum depth among all nodes.

For the case $n=3$, the final constructed tree is shown below. The depth of this tree is $3$. You need to choose a depth $k$ and prune (remove) all nodes whose depth is greater than $k$, but $k$ must be greater than or equal to $1$ and less than or equal to the depth of the tree.

Xiao J also gives you a requirement: the number of nodes you prune must be at least $m$, otherwise he will not be happy. You need to maximize the tree’s beauty value while ensuring that he is happy.

Now Xiao J gives you the parameter $n$ for building the tree and the minimum number of nodes to prune $m$. You need to find the maximum possible beauty value after pruning. If no matter what you do, you cannot make Xiao J happy, output $-1$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

There is one line containing two integers $n,m$, representing the construction parameter of the binary tree and the minimum number of nodes you must prune.

Output Format

For each test case, output one line containing one integer, representing the maximum beauty value you can obtain. If it is impossible to make Xiao J happy, output $-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

Hint

Sample Explanation #1

For the first group of samples, $n$ is $3$, and the constructed tree is the same as shown in the statement.

If we choose to prune all nodes with depth greater than $1$, then we prune $2,3,4,5$, a total of $4$ nodes, and the beauty value is $1$.

If we choose to prune all nodes with depth greater than $2$, then we prune $4,5$, a total of $2$ nodes, and the beauty value is $\lfloor \dfrac{1+2+3}{2}\rfloor = 3$.

If we choose to prune all nodes with depth greater than $3$, then we do not prune any nodes, and the beauty value is $\lfloor \dfrac{1+2+3+4+5}{3}\rfloor = 5$.

Therefore, when $m=0$, the answer is $5$; when $1 \le m \le 2$, the answer is $3$; when $3 \le m \le 4$, the answer is $1$; otherwise, there is no solution and you should output $-1$.

Constraints

For all testdata, it holds that $1 \le T \le 10^5$, $1 \le n \le 10^9$, $0 \le m \le 2 \times 10^9$.

This problem uses bundled tests: test points with the same constraints are bundled into one $\text{Subtask}$.

The additional constraints for each test point are shown in the table below.

Translated by ChatGPT 5