Bathroom Stalls

A bathroom has $N + 2$ stalls in a single row. The stalls at the left and right ends are permanently occupied by the bathroom guards, and the other $N$ stalls are for users.

Whenever someone enters the bathroom, they pick a stall as far from other people as possible. The rule they follow is deterministic. For each empty stall $S$ they compute two values, $L_S$ and $R_S$. $L_S$ is the number of empty stalls between $S$ and the closest occupied stall to its left, and $R_S$ is the same count to the right. They first keep only the stalls where $\min(L_S, R_S)$ is maximal. If exactly one stall remains, they take it. Otherwise they take the one among those where $\max(L_S, R_S)$ is maximal, and if several are still tied, the leftmost one.

$K$ people enter one after another. Each person picks a stall before the next one arrives, and nobody ever leaves.

For the stall $S$ picked by the last of the $K$ people, report $\max(L_S, R_S)$ and $\min(L_S, R_S)$.

The first line contains the number of test cases $T$. Each of the next $T$ lines describes one test case with two integers $N$ and $K$.

Limits

• $1 \le T \le 100$
• $1 \le K \le N$
• $1 \le N \le 10^6$

For each test case, print one line in the form Case #x: y z, where $x$ is the test case number starting from 1, $y$ is $\max(L_S, R_S)$ and $z$ is $\min(L_S, R_S)$ for the stall $S$ chosen by the last person to enter.

In the first test case, the first person takes the left one of the two middle stalls, which gives O.O..O. Here O is an occupied stall and . is an empty one. The second and last person then takes the stall immediately to the right, leaving 1 empty stall on one side and none on the other.

In the second test case, the first person takes the middle stall, which gives O..O..O. The second and last person then takes the leftmost stall.

In the third test case, the first person takes the left one of the two middle stalls, which gives O..O...O. The second person takes the middle of the three consecutive empty stalls.

In the fourth test case, every stall ends up occupied no matter which stalls are chosen.

In the fifth test case, the only person takes the left one of the two middle stalls.