402887: GYM100935 H Bend Test

Feras, our beloved chef judge, bought a brand new iPhone 6 plus. he put some music on and went for a ride. Unfortunately when he got back, he found out that his new smart phone has bent !! He was furious, luckily he -like all chef judges- was a rich investor, he decided to make his own phone, he called his friends in HMK faculties, bought a factory and created some identical prototypes.

Feras, as a software engineer, knows very well the importance of testing new products, as well as his own only rule “never trust a HMK student with your money” decided to put those prototypes into real life test.

He bought a device to carry out the most important test of all tests, aka “The Bend Test”.

this device has exactly m pressure values to apply on the poor phone, 1,2,…,m. obviously if the phone bends, you cannot test it again. Also if the phone bends for a pressure value x, it will also bend for a any pressure value  ≥  x. you can assume that the prototypes are identical ( which means they will bend for the same pressure values).

the ultimate goal of this problem is , given m and p (the number of prototypes), to help Feras know the minimum number of tests (in the worst case) he needs to carry out, in order to know the lowest pressure value on which the new phone will bend.

for example if m=100 and he has one prototype (p=1) then ,in the worst case, he needs 100 tests. trying the pressure values from 1 to 100 in sequence. However, in the case where he has 2 prototypes (p=2, m=100 still) and tried the first for a pressure value x, if it bends then he is in the case where he has one prototype remaining and he has to test it for values from 1 to x-1 in sequence, yielding x tests in total in the worst case (the first prototypes tested once,the second at most x-1). However, if the first prototype does not beak when tested for value x, he reduced the problem to test pressure values from x+1 to 100 (we must keep in mind that he used one test). in result the minimum number of tests, in the worst case, is the minimum over all x.

The first line of input contains a single integer C, ( 1  ≤  C  ≤  1000), which is the number of test cases.The following lines of input represent the test cases. Each test case consist of a single line containing two integers: P the number of prototypes ( 1  ≤  P  ≤  50 ), followed by a space, followed by M (1  ≤  M  ≤  1000).

For each test case print on line of output in the following format: "Case c: v"   where c is an integer represent the test case number and v is the minimum number of tests needed in the worst case.

4
2 10
2 100
2 300
25 900

Case 1: 4
Case 2: 14
Case 3: 24
Case 4: 10