Snapper Chain (Hard)

*Note that this is a harder version of the problem
snappereasy*

The *Snapper* is a clever little device that, on one
side, plugs its input plug into an output socket, and, on the
other side, exposes an output socket for plugging in a light or
other device.

When a *Snapper* is in the ON state and is receiving
power from its input plug, then the device connected to its
output socket is receiving power as well. When you snap your
fingers – making a clicking sound – any *Snapper*
receiving power at the time of the snap toggles between the ON
and OFF states.

In hopes of destroying the universe by means of a
singularity, I have purchased $N$ *Snapper* devices and
chained them together by plugging the first one into a power
socket, the second one into the first one, and so on. The light
is plugged into the $N$th
*Snapper*.

Initially, all the *Snapper*s are in the OFF state,
so only the first one is receiving power from the socket, and
the light is off. I snap my fingers once, which toggles the
first *Snapper* into the ON state and gives power to the
second one. I snap my fingers again, which toggles both
*Snapper*s and then promptly cuts power off from the
second one, leaving it in the ON state, but with no power. I
snap my fingers the third time, which toggles the first
*Snapper* again and gives power to the second one. Now
both *Snapper*s are in the ON state, and if my light is
plugged into the second *Snapper* it will be
*on*.

I keep doing this for hours. Will the light be *on*
or *off* after I have snapped my fingers $K$ times? The light is *on* if
and only if it’s receiving power from the *Snapper* it’s
plugged into.

The first line of the input gives the number of test cases, $T$. $T$ lines follow. Each one contains two integers, $N$ and $K$.

You may assume that $1 \leq T \leq 10\, 000$, $1 \leq N \leq 30$ and $0 \leq K \leq 10^{8}$.

For each test case, output one line containing “Case #$x$: $y$”, where $x$ is the case number (starting from 1) and $y$ is either "ON" or "OFF", indicating the state of the light bulb.

Sample Input 1 | Sample Output 1 |
---|---|

4 1 0 1 1 4 0 4 47 |
Case #1: OFF Case #2: ON Case #3: OFF Case #4: ON |