Consider a graph G(V,E) where V is the set of natural numbers and E, the set of edges is formed as follows: A vertex x is said to be an ancestor of y(not equal to x) if y divides x i.e., x is a multiple of y. A vertex x is said to be a parent of y if x is an ancestor of y and there is no vertex z such that z is an ancestor of y and x is an ancestor of z. If x is a parent of y, then y is said to be a child of x. It is easy to observe that every vertex has infinitely many parents but finitely many children. A pair (u,v) belongs to E if either u is a parent of v or v is a parent of u.
For example, 4 is a parent of 2 and 8 is a parent of 4 but 8 is not a parent of 2.
Enough of the definitions!! Now let us jump into the problem. Given two numbers u and v, your objective is to find the minimum number of edges that need to be traversed to go from u to v using the edges of G.
Input:
The first line of each test case begins with an integer T denoting the number of test cases. T lines follow each containing a pair of space separated integers u and v denoting the pair of integers for which you have to find the minimum number of edges required to go from u to v.
Output:
Output T lines each containing a single integer denoting the minimum number of edges that have to be traversed to go from u to v corresponding to each test case.
Constraints:
1 <= T <= 100000 (10^5)
1 <= u, v <= 10000000 (10^7)
In the first case, we are already at the destination vertex so the answer is zero. In the second case, we could use the edge connecting 2 and 4 to go from 2 to 4. There exists such an edge as 4 is a parent of 2. In the third case, we could either use 2->10->30 or 2->6->30. No other path uses lesser number of edges.
