Candy Store (Small)

Running a candy store means optimizing one thing after another. The best seller right now is a candy called Whizboppers. Whizboppers go rotten very quickly, which forces two rules on you.

• You must buy new Whizboppers from your supplier every morning.
• You must sell Whizboppers only out of the boxes you bought that morning.

You can order a box of any weight from your supplier, as long as the weight is an integer number of grams. A box cannot be split, so a customer always receives whole boxes.

Up to $k$ people visit your store each day. Starting from the first person, each one picks an integer amount to spend on Whizboppers, between $1$ and $C$ cents inclusive. Whizboppers cost $1$ cent per gram, so a person who wants to spend $4$ cents must receive exactly $4$ grams. You may hand over one 4-gram box, or one 2-gram box and two 1-gram boxes.

Whatever amounts the people pick, you have to give every one of them the exact mass they paid for. Find the minimum number of boxes you need to order in the morning.

Note: when a person picks an amount, you know what the earlier people bought, but you do not know what the later people will buy.

For example, take $k=2$ and $C=2$. Four 1-gram boxes are enough, but two 1-gram boxes and one 2-gram box, three boxes in total, also work.

• If the first person spends $2$ cents, give the 2-gram box. The two remaining 1-gram boxes cover both $1$ cent and $2$ cents for the second person.
• If the first person spends $1$ cent, give one 1-gram box. The remaining 1-gram box and 2-gram box cover both $1$ cent and $2$ cents for the second person.

Whatever the first person picks, the second person still gets an exact mass, so the answer for $k=2$, $C=2$ is $3$.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $k$ and $C$: the largest number of people that may visit in one day, and the largest amount one person may spend.

Limits

• $1 \le T \le 100$
• $1 \le k \le 20$
• $1 \le C \le 3$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from $1$ and $y$ is the minimum number of boxes you need to order every morning.

In the first case, one 1-gram box and one 2-gram box cover $1$, $2$ and $3$ cents. In the second case, buy two 1-gram boxes and one 2-gram box. In the fourth case, two 1-gram boxes, one 2-gram box and one 3-gram box handle both people.