The Mailboxes Manufacturers Problem

<span lang="en-us"><p>In the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with <i>k</i> (1 &le; <i>k</i> &le; 10) identical mailbox prototypes each fitting up to <i>m</i> (1 &le; <i>m</i> &le; 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, &ldquo;Well,if I blow up a mailbox I can&rsquo;t use it again, so if you would provide me with only <i>k</i> = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up even when filled with m crackers, I would need 1 + 2 + 3 + &hellip; + <i>m</i> = <i>m</i> &times; (<i>m</i> + 1) &frasl; 2 crackers. If <i>m</i> = 100 that would mean more than 5000 fire-crackers!&rdquo; &ldquo;That&rsquo;s too many,&rdquo; he replies. &ldquo;What if I give you more than <i>k</i> = 1 mailboxes? Can you find a strategy that requires less crackers?&rdquo;</p><p>Can you? And what is the minimum number of crackers that you should ask him to provide you with?</p><p>You may assume the following:</p><ol><li>If a mailbox can withstand <i>x</i> fire-crackers, it can also withstand <i>x</i> &minus; 1 fire-crackers.</li><li>Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.</li></ol><p>Note: If the mailbox can withstand a full load of <i>m</i> fire-crackers, then the manufacturer will of course be satisfied with that answer. But otherwise he is looking for the maximum number of crackers that his mailboxes can withstand.</p></span>

<span lang="en-us"><p>The input starts with a single integer <i>N</i> (1 ≤ <i>N</i> ≤ 10) indicating the number of test cases to follow. Each test case is described by a line containing two integers: <i>k</i> and <i>m</i>, separated by a single space.</p></span>

<p>For each test case print one line with a single integer indicating the minimum number of fire-crackers that is needed, in the worst case, in order to figure out how many crackers the mailbox prototype can withstand.</p>

4
1 10
1 100
3 73
5 100

55
5050
382
495

PKU