#1598 DivisorInc

22  30 s   128 MB  

Description

There is an integer K. You are allowed to add to K any of its divisors not equal to 1 and K. The same operation can be applied to the resulting number and so on. Notice that starting from the number 4, we can reach any composite number by applying several such operations. For example, the number 24 can be reached starting from 4 using 5 operations: 4->6->8->12->18->24.

You will solve a more general problem. Given ints N and M, print the minimal number of the described operations necessary to transform N into M. Print -1 if M can't be obtained from N.

Input

The first line of the input gives a number of test cases, T (1 <= T <= 500).
The first line of each case is consists of 2 integers. N, M (4 <= N <= M <= 100,000).

Output

For each test case, print the minimal number of the described operations necessary to transform N into M. Print -1 if M can't be obtained from N.

Sample Input

Sample Output

6
4 24
4 576
8748 83462
235 98234
4 99991
82736 82736
5
14
10
21
-1
0

HINT

* 1st test case : The example from the problem statement.
* 2nd test case : The shortest order of operations is: 4->6->8->12->18->27->36->54->81->108->162->243->324->432->576.
* 3rd test case : The shortest order of operations is: 8748->13122->19683->26244->39366->59049->78732->83106->83448->83460->83462.
* 5th test case : The number 99991 can't be obtained because it is prime.
* 6th test case : We don't need any operations. N and M are already equal.

Source

Topcoder SRM