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 ≤ 106, 1 ≤ T ≤ 40 000.
Przykład
| Wejście | Wyjście | |
|
|