Candy Store (Large)

Running a candy store means optimizing a lot of things. The candy that sells best right now is the Whizbopper, and it goes rotten very quickly, which forces two rules on you.

• Every morning you buy fresh Whizboppers from your supplier.
• You sell Whizboppers in the boxes you bought that morning.

You can order boxes that contain any integer number of grams. A box cannot be opened or split, so a customer always receives whole boxes.

Up to $k$ customers visit the store in one day. Starting with the first one, each customer picks an integer amount between $1$ and $C$ cents and buys that much candy. Candy sells for $1$ cent per gram, so a customer who spends $4$ cents gets exactly $4$ grams. You can hand over one $4$ gram box, or one $2$ gram box and two $1$ gram boxes.

What is the smallest number of boxes you have to order in the morning so that every customer gets exactly the mass they ask for, whatever the amounts turn out to be?

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

For example, suppose at most two customers come in a day and each spends at most $2$ cents ($k=2$, $C=2$). Four $1$ gram boxes work, but three boxes are enough: two $1$ gram boxes and one $2$ gram box. Hand them out like this.

Whatever the first customer picks, the second customer still gets an exact mass, so three boxes cover every order sequence for $k=2$, $C=2$. For $k=1$, $C=5$, one $1$ gram box and two $2$ gram boxes are enough.

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 customers in a day and the largest amount one customer may spend.

Limits

• $1 \le T \le 100$
• $1 \le k \le 1000$
• $1 \le C \le 10^{12}$

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.