Shortest path

Problem Description

Forever-chicken has recently been studying a lot of single-source shortest path algorithms, such as Dijkstra's algorithm, Bellman-Ford algorithm, and so on. To test the accuracy and efficiency of these algorithms, he generated his own directed graph with $n$ vertices(numbered from $1$ to $n$) using the following method:

• For each vertex $i(1\le i\le n/2)$, there is a directed edge from $i$ to $2*i$.
• For each vertex $i(1\le i\le n/3)$, there is a directed edge from $i$ to $3*i$.
• For each vertex $i(1\le i\le n-1)$, there is a directed edge from $i$ to $i+1$. Now he wants to know the length of the shortest path from vertex $1$ to vertex $n$. Can you help him with this?

Input

Each test contains multiple test cases. The first line of input contains a single integer $t(1\le t\le 2000)$ -- the number of test cases. Each test case consists of an integer $n(1\le n \le 10^{18})$, representing the number of vertices of the graph.

Output

For each test case, output a positive integer representing the distance from vertex $1$ to vertex $n$.

Sample Input

4
7
114514
1919810
2147483648

Sample Output

3
19
20
31

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）