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

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 )

Jaka jest minimalna liczba cięć, którą należy wykonać, aby wśród powstałych w wyniku cięć desek istniał podzbiór o długościach sumujących się do K?

입력 형식

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

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.

출력 형식

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

예제 입력

2
3
4

예제 출력

2
0