#I. JIXMPII5JUkT7UV#'?/
JIXMPII5JUkT7UV#'?/
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Statement
Johnny has recently found an ancient, broken computer. The machine has only one register, which allows one to put in there one variable. Then in one operation, you can shift its bits left or right by at most three positions. The right shift is forbidden if it cuts off some ones. So, in fact, in one operation, you can multiply or divide your number by , or , and division is only allowed if the number is divisible by the chosen divisor.
Formally, if the register contains a positive integer , in one operation it can be replaced by one of the following:
- , if is divisible by
- , if is divisible by
- , if is divisible by
For example, if , in one operation it can be replaced by , , or . Value isn't divisible by or , so there're only four variants of replacement.
Now Johnny wonders how many operations he needs to perform if he puts in the register and wants to get at the end.
Format
Input
The input consists of multiple test cases. The first line contains an integer ( ) — the number of test cases. The following lines contain a description of test cases.
The first and only line in each test case contains integers and ( ) — the initial and target value of the variable, respectively.
Output
Output lines, each line should contain one integer denoting the minimum number of operations Johnny needs to perform. If Johnny cannot get at the end, then write .
Sample
10
10 5
11 44
17 21
1 1
96 3
2 128
1001 1100611139403776
1000000000000000000 1000000000000000000
7 1
10 8
1
1
-1
0
2
2
14
0
-1
-1
ShanghaiTech ACM 炸鱼杯
- 状态
- 已结束
- 规则
- OI
- 题目
- 46
- 开始于
- 2024-12-10 23:00
- 结束于
- 2024-12-15 13:00
- 持续时间
- 110 小时
- 主持人
-
_Arahc_
- 参赛人数
- 112