
ZOJ Problem Set  3407
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:
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. InputThis 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. OutputFor 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 Input3 5 3 4 2 5 1 Sample Output1 0 1 Author: WU, Jun Contest: ZOJ Monthly, October 2010 