{"raw_statement":[{"iden":"statement","content":"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.\n\nFeras, 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.\n\nHe bought a device to carry out the most important test of all tests, aka “The Bend Test”.\n\nthis 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).\n\nthe 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.\n\nfor 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.\n\nThe 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).\n\nFor 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.\n\n"},{"iden":"input","content":"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)."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input42 102 1002 30025 900OutputCase 1: 4Case 2: 14Case 3: 24Case 4: 10"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ P \\in \\mathbb{Z}^+ $ be the number of prototypes.  \nLet $ M \\in \\mathbb{Z}^+ $ be the number of pressure levels, labeled $ 1, 2, \\dots, M $.  \nLet $ f(p, m) $ denote the minimum number of tests in the worst case to determine the critical pressure (lowest pressure at which the phone bends), given $ p $ prototypes and $ m $ pressure levels.\n\n**Constraints**  \n1. $ 1 \\leq C \\leq 1000 $ (number of test cases)  \n2. For each test case:  \n   - $ 1 \\leq P \\leq 50 $  \n   - $ 1 \\leq M \\leq 1000 $\n\n**Objective**  \nCompute $ f(P, M) $, defined recursively by:  \n$$\nf(p, m) = \n\\begin{cases}\n0 & \\text{if } m = 0 \\\\\nm & \\text{if } p = 1 \\\\\n\\min_{1 \\leq x \\leq m} \\left( 1 + \\max\\left(f(p-1, x-1), f(p, m-x)\\right) \\right) & \\text{if } p > 1 \\text{ and } m > 0\n\\end{cases}\n$$\n\n**Input Format**  \nEach test case: $ P \\ M $\n\n**Output Format**  \nFor each test case $ c $: `\"Case c: v\"` where $ v = f(P, M) $","simple_statement":"You have P identical phone prototypes and a device that can test pressures from 1 to M.  \nIf a phone breaks at pressure x, it breaks at all higher pressures too.  \nYou want to find the lowest pressure that breaks the phone.  \nEach test uses one phone — if it breaks, you lose it.  \nWhat’s the minimum number of tests needed in the worst case?","has_page_source":false}