h2. Cerintă

Pentru fiecare dintre cele *Q* clădiri din Liftopolis, precizată prin nivelul la care se află uşa de ieşire din clădire, să se determine numărul minim de comenzi precum şi comenzile pe care Vellipo le va da pentru a ajunge la nivelul de ieşire.

Pentru fiecare dintre cele *Q* clădiri din Liftopolis, precizată prin nivelul la care se află uşa de ieşire din clădire, să se
determine numărul minim de comenzi precum şi comenzile pe care Vellipo le va da pentru a ajunge la nivelul de ieşire.

h2. Date de intrare

Fişierul de intrare lift.in conţine pe prima linie un număr natural Q ce reprezintă numărul de clădiri. Pe fiecare dintre următoarele Q linii se află câte un număr întreg N ce reprezintă nivelul la care se află uşa de ieşire din clădire.

Fişierul de intrare $lift.in$ conţine pe prima linie un număr natural Q ce reprezintă numărul de clădiri. Pe fiecare
dintre următoarele *Q* linii se află câte un număr întreg N ce reprezintă nivelul la care se află uşa de ieşire din clădire.

h2. Date de ieşire

h2. Restricţii
* 1 ≤ Q ≤ 50.000

* pentru 20% dintre teste |*N*| ≤ 55 si |*Q*| ≤ 40
* pentru 40% dintre teste |*N*| ≤ 5000 si |*Q*|≤ 50000
* pentru 100% dintre teste |*N*| ≤ 10 15 si |*Q*| ≤ 50000
* Şirul lui Fibonacci: f~1~ =1, f~2~ =1, iar termenul de rang n este construit cu ajutorul relaţiei f~n~ =f~n-1~ +f~n-2~ , n≥3

* pentru 20% dintre teste |N| ≤ 55 si |Q| ≤ 40
* pentru 40% dintre teste |N| ≤ 5000 si |Q|≤ 50000
* pentru 100% dintre teste |N| ≤ 10 15 si |Q| ≤ 50000
* Şirul lui Fibonacci: f ~1~ =1, f ~2~ =1, iar termenul de rang n este construit cu ajutorul relaţiei f ~n~ =f ~n-1~ +f ~n-2~ , n≥3

h2. Exemplu