\textit{Это интерактивная задача.}

Определим функцию Коллатца $\mathrm{collatz}(x)$, действующую на целых числах, так: если $x$ чётное, то $\mathrm{collatz}(x) = \frac{x}{2}$, а иначе $\mathrm{collatz}(x) = 3x + 1$. Знаменитая гипотеза Коллатца гласит, что, если начать с любого целого положительного $x_0$ и построить последовательность $x_1 = \mathrm{collatz}(x_0)$, \ldots, $x_{i + 1} = \mathrm{collatz}(x_i)$, то в этой последовательности обязательно встретится единица.

Невероятная сложность, из-за которой гипотеза до сих пор ни доказана, ни опровергнута, заключается в очень хаотичном поведении последовательности $\left\{x_i\right\}$ до момента, когда она достигает единицы. Даже для очень небольших чисел единица может достигаться довольно поздно: так, если стартовать с $x_0 = 9$, получим $$9 \to 28 \to 14 \to 7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1\text{,}$$ а если начать с $x_0 = 27$, то получим единицу лишь после 111 применений $\mathrm{collatz}(x)$!

Вы сидите перед автоматом, у которого есть экран и две кнопки: красная и синяя. На экране отображается целое положительное число (гарантируется, что это случайное число от $2$ до $10^7$ включительно), и его вам надо превратить в единицу. Красная кнопка называется \texttt{collatz}, она заменяет число $x$ на экране на $\mathrm{collatz}(x)$. Синяя кнопка называется \texttt{random}, она заменяет $x$ на случайное целое число от $3x + 1$ до $6x$ включительно. Нажатия на кнопки не бесплатны: после каждого нажатия кнопки, когда на экране отображается число $x_{i + 1}$, требуется внести в автомат столько жетонов, сколько цифр в десятичной записи числа $x_{i + 1}$. Например, в вышеприведённом процессе, стартующем с девятки, нужно заплатить за все цифры чисел $28, 14, 7, \ldots, 2, 1$; на это уйдёт 32 жетона.

Если нажимать только на красную кнопку, вы достигнете единицы, потратив в среднем 707 жетонов. Несмотря на то, что синяя кнопка всегда увеличивает число на экране (причём значительно), можно ускорить процесс получения единицы, если в правильные моменты нажимать синюю кнопку! Ваша задача~--- написать программу, которая тратит на одно число в среднем не более 600 жетонов. Чтобы проверка меньше зависела от случайности, мы в каждом тесте дадим программе $t \le 50$ случайных стартовых чисел, и вам надо будет превратить их все в единицы за $600 \cdot 50 = 30\,000$ жетонов.