Locked Treasure

A group of $n$ bandits ($1 \le n \le 30$) hid their stolen treasure in a room. The treasure stays locked away until someone needs to retrieve it. The bandits do not trust each other, so they want a rule that at least $m$ of them ($1 \le m \le n$) must agree before the treasure comes out.

They decided to put several locks on the door, and the door opens only when every lock is open. Each lock can have up to $n$ keys, handed out to some of the bandits. A group opens a given lock only if at least one bandit in the group holds a key to it.

You are given $n$ and $m$. Find the minimum number of locks such that the keys can be distributed so that every group of $m$ or more bandits opens all the locks, and no smaller group opens all the locks.

For example, with $n = 3$ and $m = 2$, three locks are enough. Give the keys of lock 1 to bandits 1 and 2, the keys of lock 2 to bandits 1 and 3, and the keys of lock 3 to bandits 2 and 3. A single bandit cannot open all the locks, and any two bandits together can. Two locks are not enough to meet the requirement.

The first line contains a positive integer, the number of test cases. Each test case is one line holding the two integers $n$ and $m$.

For each test case, print the minimum number of locks needed on its own line.