Deski

Deski

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów

Kapitan Pitt postanowił zbudować płot. Jednym z problemów które musi rozwiązać jest zdobycie desek o łącznej długości K. 

Sprawa nie jest prosta, bo Kapitan Pitt ma do dyspozycji tylko:

• Maszynę, która może przeciąć dowolną deskę dokładnie na pół
• Jedną deskę o długości będącej dowolną, wskazaną przez Kapitana Pitta potęgą dwójki ( dostarczy ją znajomy stolarz )

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ). Następnie opisywane są kolejne zestawy testowe.

W pierwszej linii opisu zestawu znajduje się liczba naturalna K ( 1 <= K <= 1 000 000 000 000 ), oznaczająca łączną długość desek, której potrzebuje Kapitan Pitt.

Wyjście

Dla każdego zestawu należy w osobnej linii wypisać jedną liczbę, będącą minimalną liczbą cięć, które musi wykonać Kapitan Pitt.

Przykład