Đường đi ít chi phí nhất trong bài mọi con đường về không
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
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 29Output
33
66
-1Giả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
Comments
cho em xin code bài này với ạ