Tháp Khổng Lồ
Ngày xưa ở một vương quốc nọ có một cô công chúa và anh chàng tiểu phu nghèo.
Do cô công chúa bị dính lời nguyền trên chiếc tháp khổng lồ nên rất hay đau bụng và không chịu ăn cơm.Vào một ngày nọ, quốc vương tuyên bố ai là người giải được lời nguyền này thì sẽ cưới được công chúa và sống sung sướng giàu sang cả đời.Nhưng để leo lên được chiếc tháp khổng lồ đấy và giải được lời nguyền, thì phải leo qua những bậc thang và tuân thủ theo những luật lệ mà tháp khổng lồ đặt ra, nếu không sẽ bị chết.Tháp có n bậc thang và mỗi lần người leo tháp chỉ có thể leo 1 bậc hoặc 2 bậc trong mỗi lần di chuyển, đồng thời phải thõa mãn sau khi lên được tháp số lần di chuyển phải là nhỏ nhất và là bội của số nguyên dương m. Vì ngày mai đã đến ngày thi rồi nhưng anh chàng tiều phu nghèo kia vẫn chưa có cách nào leo lên được,các bạn hãy giúp anh chàng tiểu phu để anh ta đổi đời nhé.
Lưu ý : Chỉ được bước tiến lên không được bước lùi.
Input
- Dòng đầu tiên chứa số nguyên T đại diện cho số bộ test \((1 \le T \le 10^6)\).
- T dòng tiếp theo mỗi dòng lần lượt nhập vào hai số nguyên n, m \((1 \le n , m \le 10^9)\).
Ouput
- Mỗi test in ra số bước di chuyển tối thiểu thõa mãn điều kiện trên nếu không có cách nào thõa mãn được yêu cầu thì in ra -1 trên một dòng.
Ví dụ :
Input1
3
11 4
2 6
33 23Output1
8
-1
23Input2
2
101 50
3 99Output2
100
-1
Comments
C++ nhập xuất bằng printf với scanf hoặc dùng đồng bộ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); để tránh tle