22 30 s 128 MB

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.

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).

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 |

* 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.