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.

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.

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