Problem description

Do Twardowskiego to mi jednak trochę brakuje, ten to wiedział, jak sprawnie umknąć wierzycielom – tak właśnie myślał sobie Ban Bajtolo, kiedy był prowadzony przed oblicze Wielkiego Jaszczura – no cóż, przynajmniej ja nikomu duszy nie obiecywałem.

Wielki Jaszczur nie był w humorze do podejmowania poważnych decyzji, więc stwierdził, że kłopotliwy dłużnik zostanie zamrożony i przechowany w specjalnym magazynie przez N lat, a potem się zobaczy. Magazynier zabrał Bana Bajtolo i umieścił go w maszynie hibernującej. Jej obsługa jest dość prosta, wystarczy podać liczbę lat, po której zawartość ma być rozmrożona, a następnie wcisnąć enter. Niestety, urządzenie jest wiekowe i przyjmuje wejście tylko w systemie jedynkowym (I to jeden, II to dwa, a IIIIIIIIIIIIIIII oznacza szesnaście). Na ekranie początkowo znajduje się I (zapis liczby jeden), magazynier może zmieniać tę wartość przy użyciu następujących operacji:

• zaznacz wszystko – zaznacza całą zawartość ekranu,
• kopiuj – umieszcza zaznaczoną część napisu w schowku, który początkowo jest pusty,
• wklej – dopisuje zawartość schowka na koniec liczby znajdującej się na ekranie.

Jakiej minimalnej liczby powyższych trzech operacji magazynier potrzebuje, żeby na ekranie pojawił się zapis liczby N?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna T oznaczająca liczbę zapytań. Każdy z kolejnych T wierszy opisuje jedno zapytanie i składa się z jednej liczby naturalnej N – pożądanej długości hibernacji Bana Bajtolo.

Wyjście

Dla każdego zapytania w osobnym wierszu wyjścia należy wypisać jedną liczbę naturalną – minimalną liczbę operacji potrzebną do uzyskania zapisu odpowiedniej liczby.

Ograniczenia

1 ≤ N ≤ 10⁶, 1 ≤ T ≤ 40 000.

Przykład

2
2
3

3
4