Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
The missionaries and cannibals
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 285Accepted: 78

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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator