F. 0, 1, 2, Tree!

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

Find the minimum height of a rooted tree${}^{†}$ with $a+b+c$ vertices that satisfies the following conditions:

• $a$ vertices have exactly $2$ children,
• $b$ vertices have exactly $1$ child, and
• $c$ vertices have exactly $0$ children.

If no such tree exists, you should report it.

The tree above is rooted at the top vertex, and each vertex is labeled with the number of children it has. Here $a=2$, $b=1$, $c=3$, and the height is $2$.

${}^{†}$ A rooted tree is a connected graph without cycles, with a special vertex called the root. In a rooted tree, among any two vertices connected by an edge, one vertex is a parent (the one closer to the root), and the other one is a child.

The distance between two vertices in a tree is the number of edges in the shortest path between them. The height of a rooted tree is the maximum distance from a vertex to the root.

Input

The first line contains an integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The only line of each test case contains three integers $a$, $b$, and $c$ ($0\le a,b,c\le 10^5$; $1\le a+b+c$).

The sum of $a+b+c$ over all test cases does not exceed $3\cdot 10^5$.

Output

For each test case, if no such tree exists, output $-1$. Otherwise, output one integer — the minimum height of a tree satisfying the conditions in the statement.

Example
inputCopy
10
2 1 3
0 0 1
0 1 1
1 0 2
1 1 3
3 1 4
8 17 9
24 36 48
1 0 0
0 3 1
outputCopy
2
0
1
1
-1
3
6
-1
-1
3

AC代码：

#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
//#define endl '\n'
using namespace std;typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e8 + 10;//树的构造
int t;
int main()
{cin >> t;while(t --){int a, b, c;cin >> a >> b >> c;int len = 0, num = 1;if(a + 1 != c) puts("-1");else {while(a){if(a >= num){a -= num;num *= 2;}else {int nex = num + a;num -= a;a = 0;int l =min(num, b);b -= l;num = nex;}len ++;}while(b > 0){b -= num;len ++;}cout << len << endl;}}return 0;
}