Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
The missionaries and cannibals
 Time Limit: 10000MS Memory Limit: 65536K Total Submissions: 907 Accepted: 90

Description

The missionaries and cannibals problem is usually stated as follows: Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. Now the problem has been extended to be more complicated. There are m missionaries and m cannibals who want to cross the river. And the boat is also enlarged to be capable of supporting n people. In order to make all of them cross the river safely what is the least number of steps? Notice that when the boat goes across the river there must be at least one missionary or cannibal on the boat.

Input

The first line of the input is an integer T which indicates the number of test cases. Each test case is specified on a separate line and is made of two positive number m and n, where m ≤ 100000 and n ≤ 1000.

Output

For each test case, output the result on a single line. If the problem can't be solved, print -1 as the result.

Sample Input

```2
3 2
20 3
```

Sample Output

```11
-1
```

Source

[Submit]   [Go Back]   [Status]   [Discuss]