Question
Minimum Operations to Convert A to B
You are given two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. You can perform the following two operations on KaTeX can only parse string typed expression:
- Add KaTeX can only parse string typed expression to KaTeX can only parse string typed expression.
- Multiply KaTeX can only parse string typed expression by KaTeX can only parse string typed expression.
Your task is to find the minimum number of operations required to transform KaTeX can only parse string typed expression into KaTeX can only parse string typed expression. If it is not possible, print KaTeX can only parse string typed expression.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of test cases.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Output
For each test case, print a single integer — the minimum number of operations required to convert KaTeX can only parse string typed expression into KaTeX can only parse string typed expression, or KaTeX can only parse string typed expression if it is not possible.
Example
Input
3
2 7
4 20
5 3
Output
3
3
-1
Explanation
Test case 1:
2 → 3 → 6 → 7 (3 steps)
Test case 2:
4 → 5 → 10 → 20 (3 steps) OR
4 → 8 → 9 → 18 → 20 (4 steps, not optimal)
Minimum = 3 steps
Test case 3:
It is not possible to reduce KaTeX can only parse string typed expression, so answer is KaTeX can only parse string typed expression.
3
2 7
4 20
5 3
Output
3
3
-1
Explanation
Test case 1:
2 → 3 → 6 → 7 (3 steps)
Test case 2:
4 → 5 → 10 → 20 (3 steps) OR
4 → 8 → 9 → 18 → 20 (4 steps, not optimal)
Minimum = 3 steps
Test case 3:
It is not possible to reduce KaTeX can only parse string typed expression, so answer is KaTeX can only parse string typed expression.