In this **HackerEarth The exam problem solution** 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.

## HackerEarth The exam problem solution.

def solve():
x, l, n = map(int, input().split())
min_erased = -1
max_erased = x
while max_erased - min_erased > 1:
erased = (min_erased + max_erased) // 2
cur_x = x - erased
good = True
for it in range(n):
if cur_x > l:
good = False
break
cur_x *= 2
if good:
max_erased = erased
else:
min_erased = erased
print(max_erased)
def main():
t = int(input())
for i in range(t):
solve()
main()