The Mailbox Manufacturers Problem

A mailbox manufacturer wants to know how many firecrackers his new mailbox prototype can withstand before it is destroyed. He gives you $k$ ($1 \le k \le 10$) identical prototypes, each able to hold up to $m$ ($1 \le m \le 100$) firecrackers, and asks you to determine the largest number of firecrackers a prototype can withstand.

You test a mailbox by placing some number of firecrackers inside and igniting them:

• If the number of firecrackers used is at most what the mailbox can withstand, the mailbox is unharmed and may be reused.
• Otherwise the mailbox is destroyed and can never be used again.

Every firecracker you ignite is consumed, whether or not the mailbox survives, so the cost of a single test equals the number of firecrackers used in it. You want a strategy that, in the worst case, spends as few firecrackers as possible while still determining the exact maximum a prototype can withstand.

You may assume:

1. If a mailbox can withstand $x$ firecrackers, it can also withstand $x - 1$ firecrackers.
2. After an ignition a mailbox is either totally destroyed or completely unharmed (and reusable).

With only $k = 1$ mailbox you must test $1$ firecracker, then $2$, and so on, one at a time; in the worst case (the mailbox survives even a full load of $m$) this costs $1 + 2 + \cdots + m = \frac{m(m + 1)}{2}$ firecrackers. With more mailboxes you can do better.

The maximum number a prototype can withstand is an integer between $0$ and $m$; if it withstands a full load of $m$, the answer for that prototype is $m$. Determine the minimum number of firecrackers that, in the worst case, is required to find this maximum.

The first line contains a single integer $N$ ($1 \le N \le 10$), the number of test cases. Each of the following $N$ lines describes one test case with two integers $k$ and $m$ separated by a single space.

For each test case, print a single line containing one integer: the minimum number of firecrackers needed, in the worst case, to determine the maximum number of firecrackers the mailbox prototype can withstand.