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 ≤ i ≤ n/2), there is a directed edge from i to 2 ∗ i. • For each vertex i(1 ≤ i ≤ n/3), there is a directed edge from i to 3 ∗ i. • For each vertex i(1 ≤ i ≤ 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?
输入格式
Each test contains multiple test cases. The first line of input contains a single integer t(1 ≤ t ≤ 2000) – the number of test cases. Each test case consists of an integer n(1 ≤ n ≤ 1018), representing the number of vertices of the graph.
输出格式
For each test case, output a positive integer representing the distance from vertex 1 to vertex n.