Salti spettacolari

Quando il Dr. Bruce Banner si trasforma nell’incredibile Hulk, acquista sempre più forza con l’andare del tempo.
Al tempo t=0 riesce a saltare un solo metro, al tempo t=1 ne salta due, al tempo t=2 ne salta quattro e così via: in generale, al tempo t ≥ 0, riesce a saltare 2t metri.
Tuttavia l’incredibile Hulk può saltare sempre e solo nella stessa direzione: dunque ad ogni istante t può decidere se saltare in avanti alla distanza permessagli in quel momento oppure stare fermo.

Hulk deve percorrere una certa distanza D > 0, espressa in metri, e vuole effettuare il minor numero di salti.

  • Per esempio, per D=9, Hulk salta due volte (effettua un salto da 1 e uno da 8);
  • per D=7, Hulk salta tre volte (un salto da 1, uno da 2 e uno da 4);
  • per D=16, Hulk effettua il solo salto da 16.

Aiuta Hulk a calcolare quale è il minimo numero di salti che deve effettuare per coprire la distanza D.

Dati in Input

Il file input.txt è composto da una sola riga contenente un intero positivo D, che rappresenta la distanza da percorrere.

Dati in Output

Il file output.txt è composto da una sola riga che contiene il numero di salti che Hulk deve effettuare per coprire la distanza D.

Assunzioni

  • 1 <= D <= 230

 

Esempi

input.txt output.txt
1 9 2
2 7 3
3 16 1

 

Note

  • Per ogni input, esiste una sola risposta da fornire in output.