Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3407
Doraemon's Cake Machine

Time Limit: 2 Seconds      Memory Limit: 65536 KB

One day, N kids got one cake (a cylinder in shape). They decided to divide the cake so that everyone can have one piece of that cake. In the interest of fairness, pieces of the cake should be equal in size.

However, the kids had no knives to cut the cake. Luckily, Doraemon borrowed them a magic cake machine that can cut and clone cake.

To use Doraemon's cake machine, exactly M instructions must be entered. Otherwise the cake machine will destroy the cake (Doraemon's machines are not stable enough and have strange limits, you know).

For each instruction, the machine can perform one of the following actions:

  • Cut the cake vertically. The cut should be perpendicular to the top surface, and is a diameter of the circle viewed from the top.
  • Cut the cake horizontally. The cut should be parallel to the top surface.
  • Clone a piece of cake. Due to a defect in design, the machine can not perform 'cut' action after any 'clone' action.

The two kinds of 'cut' actions are shown below:

The cake is always cutted as a whole. You can not cut just one or several pieces. For example, if you cut horizontally and then vertically, you always get 4 pieces.

A 'cut' action should make the cake into more pieces (i.e. you can not cut at a same position twice). Finally, there should be exactly N pieces of cake, which are in a same size. Thus each kid can get one and no pieces of cake are left.

Since the 'clone' action is extremely slow, use it as less as possible.


This problem contains multi test cases.

The first line contains an integer T (0 ≤ T ≤ 2000), indicating the number of test cases.

Following T lines, each line contains one test case.

Each test case contains two integers N (1 ≤ N ≤ 6000000) and M (0 ≤ M ≤ 3000000), separated by one space, indicating there are N kids and M instructions should be used.


For each case, output one integer R in one line, where R is the minimal number of 'clone' instructions. If exactly N pieces of cake can not be made from exactly M instructions, output -1 instead of R.

Sample Input

5 3
4 2
5 1

Sample Output


Author: WU, Jun
Contest: ZOJ Monthly, October 2010
Submit    Status