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.