Đường đi ít chi phí nhất trong bài mọi con đường về không


Submit solution

Points: 4 (partial)
Time limit: 1.0s
Memory limit: 977M

Author:
Problem type

Số nguyên dương n nếu phân tích thành tích hai số tự nhiên \(a * b (a<=b)\) thì nó sẽ sinh ra số tự nhiên \(m=(a-1)*(b+1)\) cứ tiếp tục như vậy nếu \(m > 0\) nó tiếp tục sinh ra số tiếp theo. Bài toán đặt ra cho số n nguyên dương nó sẽ sinh ra các con và các con lại tiếp tục sinh ra các cháu ... cứ như vậy tới khi sinh ra tới các số \(0\) thì sẽ tạo thành một cây.

Biết rằng nếu chi phí để từ nút \(n=a*b\) sinh ra nút \(m = (a-1)*(b+1)\) được tính như sau

  • Nếu \(b\) chia hết cho \(a\) thì chi phí sẽ là \( b/a\)
  • Ngược lại sẽ chi phí là \(b+a\)

Ví dụ \(m= 12\) ta có cây được sinh ra như sau

enter image description here

Toto muốn biết là từ một số tự nhiên \(s\) đi đến \(f\) thì đường đi với chi phí ít nhất là bao nhiêu

Input:

Dòng đầu tiên là số bộ kiểm thử \(t (1 \le t \le 100)\)

Các dòng tiếp theo gồm \(t\) dòng mỗi dòng chứa một hai số tự nhiên \(s,f (0 \le f \le s \le 1000)\)

Output:

Gòm \(t\) dòng lần lượt tương ứng là kết quả đối với từng giá trị đầu vào trong trường hộp không đi được thì xuất ra \(-1\)

Ví dụ

Input

3
30 10
100 10
30 29

Output

33
66
-1

Giải thích

Test 1 : cách đi như sau 30->22->12->10

Test 2 : cách đi như sau 100->99->68->35->32->27->20->18->10

tichpx

Comments

There are no comments at the moment.