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$.

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

1
4
5
3
1389