a-graph-on-numbers

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)

SAMPLE INPUT
3
2 2
2 4
2 30

SAMPLE OUTPUT
0
1
2

Explanation

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.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: