문제1598--DivisorInc

1598: DivisorInc

실행시간 제한: 30 Sec  메모리사용 제한: 128 MB
제출: 71  통과: 32
[제출] [채점기록] [묻고답하기]

문제 설명

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.

입력 예시 Copy

6
4 24
4 576
8748 83462
235 98234
4 99991
82736 82736

출력 예시 Copy

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.

출처/분류