K. Three Operations

Problem Description

Given three integers $x, a, b$. You can do the following three operations several times:

• set $x$ to $x - 1$;
• set $x$ to $\lfloor \dfrac{x+a}{2} \rfloor$;
• set $x$ to $\lfloor \sqrt{x+b} \rfloor$. Calculate the smallest number of operations to set $x$ to $0$.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 2 \times 10 ^ 4$) - the number of test cases. Description of the test cases follows. The first line of each test case contains three integers $x, a, b$ ($0\leq x, a, b \leq 10 ^ {18}$).

Output

For each test case, print one integer - the smallest number of operations to set $x$ to $0$.

Sample Input

5
1 1 4
5 1 4
19 1 9
8 1 0
1145141919810 114514 1919810

Sample Output

1
4
5
3
1389

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）