SOLVE
LATER
Kate is wizard. Now she should pass the exam.
During the exam she have to go into the magic room $$N$$ times. Initially there are $$X$$ magic items in the room. Before each visit she can use magic to decrease the number of magic items in the room. For each item she spends $$1$$ mana point to destroy it. After each visit the number of magic items increases by $$2$$ times. She can't go into room if there are more than $$L$$ magic items in it. What minimum mana points does Kate need to pass the exam?
You need to solve this problem for several test cases.
$$INPUT$$
The first line of input contains single integer $$T$$ $$(1 \leq T \leq 10^{5})$$ - a number of test cases.
Then follow $$T$$ lines. The i-th of these lines contains three integers $$X_i$$, $$L_i$$ and $$N_i$$ $$(0 \leq X_i, L_i, N_i \leq 10^{18})$$.
$$OUTPUT$$
Print $$T$$ lines.
The i-th of them should contain single integer - minimum number of mana points needed to pass the exam in the i-th test case.
In the first case test Kate should destroy 1 item before the first visit.
In the second test case Kate has already passed exam.