collatz

Collatz are $T$ vectori, fiecare vector $i$ ($1 \le i \le T$) fiind format inițial din numerele naturale consecutive de la $S_i$ la $D_i$. După părerea lui, un vector îngrijit are toate elementele egale cu $1$. Deoarece lui Collatz îi plac vectorii îngrijiți, el își dorește ca toate elementele vectorilor să devină $1$, așa că transformă pe rând vectorii, aplicând pentru fiecare un număr minim de operații. O operație constă din alegerea unui element al vectorului și apoi:

• dacă elementul este par, atunci valoarea lui se înjumătățește;
• dacă elementul este impar, având inițial valoarea $x$, atunci valoarea lui devine $2 \cdot x + 2$.

Cerință

Pentru fiecare dintre cei $T$ vectori, determinați numărul minim de operații prin care poate deveni îngrijit.

Date de intrare

Fișierul de intrare collatz.in conține pe prima linie numărul $T$, cu semnificația din enunț, iar pe fiecare din următoarele $T$ linii se află câte două numere $S_i$ și $D_i$, separate prin câte un spațiu, cu semnificația din enunț pentru fiecare vector $i$.

Date de ieșire

Fișierul de ieșire collatz.out conține $T$ numere, fiecare pe câte o linie, reprezentând numărul minim cerut pentru fiecare dintre cei $T$ vectori în ordine.

Restricții și precizări

• $1 \le T \le 1 \ 000$, număr natural;
• $1 \le S_i \le D_i \le 10^{16}$ și $S_i, D_i$ sunt numere naturale, pentru orice $1 \le i \le T$.

Exemplu

collatz.in

3
2 2
4 5
1 4

collatz.out

1
9
7

Explicație

Primul vector: Vectorul inițial este $[2]$. Este nevoie de o singură operație pentru a-l transforma pe $[2]$ în $[1]$.

Al doilea vector: Vectorul inițial este $[4, 5]$. O succesiune posibilă de $9$ operații pentru a transforma vectorul în $[1, 1]$ este următoarea:

• $[4, 5] \rightarrow [4, 12]$
• $[4, 12] \rightarrow [4, 6]$
• $[4, 6] \rightarrow [4, 3]$
• $[4, 3] \rightarrow [4, 8]$
• $[4, 8] \rightarrow [4, 4]$
• $[4, 4] \rightarrow [4, 2]$
• $[4, 2] \rightarrow [4, 1]$
• $[4, 1] \rightarrow [2, 1]$
• $[2, 1] \rightarrow [1, 1]$

Al treilea vector: vectorul inițial este $[1, 2, 3, 4]$. O succesiune posibilă de $7$ operații pentru a transforma vectorul în $[1, 1, 1, 1]$ este:

• $[1, 2, 3, 4] \rightarrow [1, 2, 3, 2]$
• $[1, 2, 3, 2] \rightarrow [1, 2, 3, 1]$
• $[1, 2, 3, 1] \rightarrow [1, 2, 8, 1]$
• $[1, 2, 8, 1] \rightarrow [1, 1, 8, 1]$
• $[1, 1, 8, 1] \rightarrow [1, 1, 4, 1]$
• $[1, 1, 4, 1] \rightarrow [1, 1, 2, 1]$
• $[1, 1, 2, 1] \rightarrow [1, 1, 1, 1]$.