|
||||||||||
Shortest pathTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1371 Accepted Submission(s): 651 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
Sample Output
Source | ||||||||||
|