Description

Ishiko is opening a bracelet shop. Each bracelet she plans to sell is expressed as a ring of $N$ colored beads, with exactly $K$ green beads made of emerald, and $N-K$ remaining beads of all unique colors (neither green nor the same as any other bead in the bracelet). Ishiko has an infinite number of beads available for each of these $N - K + 1$ different colors.

Ishiko wants to exhibit one copy of every possible distinct bracelet. Two bracelets are considered distinct if one is not a cyclic rotation of the other. For instance, the two bracelets on the left are distinct, but the two bracelets on the right are not:

A vendor takes orders for triangular display cases of arbitrary positive integer heights. A case of height $H$ has $H$ rows, where the $i$th row has $2*i - 1$ slots, each slot capable of holding one bracelet. For example, a case of height $3$ is shown below and holds $1 + 3 + 5 = 9$ bracelets:

How many display cases (of possibly differing heights) will Ishiko need to buy to exhibit one copy of every possible bracelet without leaving any empty slots in the display cases?

Constraints

• $1 \le T \le 110$
• $1 \le N \le 10^9$
• $0 \le K \le N$
• The sum of $N$ across all test cases is at most $8{,}000{,}000{,}000$.

Input Format

Input begins with an integer $T$, the number of cases. For each case, there is a line containing two space-separated integers, $N$ and $K$.

Output Format

For the $i$th case, print "Case #i:" followed by a single integer, the minimum number of display cases that Ishiko needs to purchase to exhibit one copy of each bracelet.

Sample

Sample Input

4
5 3
6 3
6 2
243447 42273

Sample Output

Case #1: 1
Case #2: 2
Case #3: 4
Case #4: 4

Sample Explanation

In the first sample case, let's say that Ishiko's beads are green, blue, and red. There are $4$ possible bracelets for $N = 5$ beads with $K = 3$ green beads, $1$ red bead, and $1$ blue bead (up to rotation):

Ishiko can use a single display case of height $2$ to display these $4$ bracelets.

In the second sample case, let's say that Ishiko's beads are green, blue, red, and yellow. There are $20$ possible bracelets for $N = 6$ beads with $K = 3$ green beads, $1$ blue bead, $1$ red bead, and $1$ yellow bead. Some examples are:

Ishiko can display these bracelets if she purchases a case of height $2$ and a case of height $4$.

In the third sample case, there are $60$ possible bracelets and Ishiko needs at least $4$ display cases to display all of them. One possibility is that she buys two cases of height $1$, one case of height $3$, and one case of height $7$.