First, let's notice that, in the optimal solution, Gauss will perform the operation of the second type (leaving the current number on the board) only for one number. Let's denote with ~A~ the initial number, with ~B~ the final number, and with ~C~ the number we left on the board.

Secondly, let's notice that the number of operations between numbers ~A~ and ~C~ and between ~C~ and ~B~ is at most ~20~, because in each moment the new number is smaller than or equal to the half of the old number. It is not difficult to notice that the cost of the shortest way from ~A~ to ~C~ is equal to the cost of the shortest way from ~A/C~ to ~1~ (analogously for ~C~ and ~C/B~).

Given the specificity of the formula to calculate the costs, we see that the cost of the shortest path to ~1~ is equal for, for example, numbers ~12~ and ~18~. More precisely, let ~e_1, e_2, \dots, e_k~ be exponents of the prime numbers in the factorization of a number into prime numbers. Then the cost of the shortest path from that number to ~1~ is equal to all such numbers that have the same multiset of exponents ~\{e_1, e_2, \dots, e_k\}~. We can generate all such numbers and see that there are less than ~250~ of them. We assign to each number ~n~ the smallest number with which it shares a multiset, and denote it with ~k(n)~.

Let's summarize the results so far: The shortest path from ~A~ to ~B~ is over a number ~C~. The cost from ~A~ to ~C~ is equal to the cost from ~A/C~ to ~1~, and that is equal to the price of ~k(A/C)~ to ~1~. Analogously for ~C~ to ~B~ and ~k(B/C)~.

Let's denote with ~b[x][y][C][L]~ the shortest path from ~A~ to ~B~ such that it holds ~k(A/C) = x~ and ~k(C/B) = y~ and the total length of paths from ~A~ to ~C~ and ~C~ to ~B~ is equal to ~L~ (not counting the moves from ~C~ to itself). This array can be calculated quickly enough at the beginning of the program with one optimization - we will calculate it only for pairs ~x~ and ~y~ such that ~xy \le 1\,000\,000~, because otherwise the pairs are not useful to us.

How do we reply to queries when we have this array? Let's go over all possible ~C~ and look at the formula for the total number of moves ~L~, and denote with ~L'~ the number of moves when we leave ~C~ on the board: The total cost is ~b[x][y][C][L-L'] + L' \times cost[C]~. Now we see that, for a fixed ~L~, we need to find a pair ~(C, L')~ that minimizes the value of the upper expression, which is actually a standard problem where we need to calculate the lower hull of the lines, and for each ~L~ find the intersection of the vertical line ~x = L~ with the hull. We must also notice that all lines for a fixed ~C~ have the same slope, so it is sufficient to calculate the larger intersection of its lines with the ~y~-axis and only add that one to the hull. The queries where ~L < 20~ need to be processed separately using dynamic programming.