Planes around the World

We have many planes at a place A, each of them can fly a/b of the world with a full tank. For example, if a = 1, b = 2, each plane can cover half of the world (that is, from A to B), shown in picture 1: With the help of hi-technology, planes can exchange fuel in no time (but remember that the amount of fuel a plane can carry cannot exceed the capacity of the tank at any time!), we can use more planes to ensure that one of them flies across the whole world, and all of them are able to be back to A at last. (C is at 1/8, D is at 1/4, E at 3/4, F at 7/8) For example, 5 planes are enough for a = 1, b = 2, shown in picture 2: The picture below gives the explanation. If you can figure it out yourself, just ignore the figure below (or next page)

2/3

3/3 So complicated, right? For simplicity, we restrict the way to the following:

1. Plane #1 is the only one, which flies around the whole world.
2. Except plane #1, every plane fill other planes exactly once.
3. There are A planes that set off together with plane #1 at the same time, each of them turns back at some time, and gives as much fuel as possible evenly to other planes before it turns back.
4. There are B planes that set off separately, waiting at B places to provide fuel for plane #1. When meets plane #1, every plane turns back and gives fuel to other planes so that every plane with it has the same amount of fuel. What is the minimal number of planes required? Input The first line of the input contains a single integer t (1 ≤ t ≤ 50), the number of test cases followed. For each case, two integers a and b (0 ≤ a, b ≤ 150) are separated by a single space. Of course b will not be zero. Output For each test case, print the case number and the minimal number of planes required. If 10000 planes are not enough, output a ‘-1’. Sample Input 3 12 13 25 Sample Output Case 1: 5 Case 2: -1 Case 3: 13