The exam
Tag(s):

## Searching

Problem
Editorial
Analytics

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.

SAMPLE INPUT
2
2 5 3
6 5 0
SAMPLE OUTPUT
1
0
Explanation

In the first case test Kate should destroy 1 item before the first visit.

In the second test case Kate has already passed exam.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

November Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures