Bathroom Stalls (Large)

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 try to choose a stall that is as far from other people as possible. To avoid confusion they follow deterministic rules. 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 number of empty stalls between $S$ and the closest occupied stall to its right. They then keep the stalls whose closest neighbour is farthest away, that is, the stalls for which $\min(L_S, R_S)$ is maximal. If only one stall remains they choose it, otherwise they choose the one among those for which $\max(L_S, R_S)$ is maximal. If several stalls are still tied, they choose the leftmost one.

K people are about to enter the bathroom. Each one chooses their stall before the next arrives, and nobody ever leaves.

When the last person chooses their stall $S$, what are the values of $\max(L_S, R_S)$ and $\min(L_S, R_S)$?

The first line contains the number of test cases, T. T lines follow, one per test case. Each of those lines contains the two integers N and K described above, separated by a space.

Limits

• $1 \le T \le 100$
• $1 \le K \le N$
• $1 \le N \le 10^{18}$

For each test case, output one line containing 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.

An occupied stall is written O and an empty stall is written ..

In case 1 of the example, the first person occupies the leftmost of the middle two stalls, which gives O.O..O. The second and last person then occupies the stall immediately to the right, leaving 1 empty stall on one side and none on the other.

In case 2, the first person occupies the middle stall, which gives O..O..O. The second and last person occupies the leftmost stall.

In case 3, the first person occupies the leftmost of the two middle stalls, which gives O..O...O. The second person occupies the middle of the three consecutive empty stalls.

In case 4, every stall is occupied at the end, no matter which stalls the people choose.

In case 5, the first and only person chooses the leftmost of the middle two stalls.