Tort

Construim un tort. Pornim cu o foaie de grosime $A$. Putem efectua una din două operații posibile:

• Împăturim tortul, îndoind foaia pe din două. Grosimea tortului se dublează.
• Adăugăm un strat de unt pe deasupra. Stratul de unt are grosime $B$. Grosimea tortului crește cu $B$.

Cerință

1. Dându-se $A$, $B$ și $C$ să se spună care este grosimea minimă a unui tort ce are grosime cel puțin egală cu $C$.
2. Dându-se $A$, $B$ și $C$ să se spună care este numărul minim de operații în care se poate obține accea grosime minimă.

Date de intrare

Pe prima linie a fișierului de intrare tort.in se vor găsi numărul cerinței, $P$, și numărul de teste, $T$. Pe următoarele $T$ linii se vor găsi triplete $A$ $B$ $C$.

Date de ieșire

În fișierul de ieșire tort.out afișați răspunsul cerut pentru fiecare triplet de la intrare, câte unul pe linie.

Restricții și precizări

• $1 \leq A, B \leq 10^9$
• $max(A, B) \leq C \leq 10^{17}$
• $0 \leq T \leq 10^6$

Exemplul 1

tort.in

1 2
90 100 480
15 25 507

tort.out

480
510

Explicație

$480 = (90 + 100) \times 2 + 100$
$510 = [(15 + 25 + 25 + 25 + 25) \times 2 + 25] \times 2$

Exemplul 2

tort.in

2 2
90 100 480
15 25 507

tort.out

3
7

Exemplul 3

tort.in

1 1
10 10 632

tort.out

640

Explicație

$640 = 10 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$ sau $640 = (10 + 10) \times 2 \times 2 \times 2 \times 2 \times 2$

Exemplul 4

tort.in

2 1
10 10 632

tort.out

6

Exemplul 5

tort.in

2 1
3 7 767

tort.out

8

Explicație

Tortul va avea grosime minimă $768$, obținută astfel: $768 = 3 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$