Snapper Chain (Large)

A Snapper is a small device with an input plug on one side and an output socket on the other. You push the input plug into some output socket, and you plug a light or another device into the Snapper's output socket.

A Snapper that is ON and receiving power passes power to whatever sits in its output socket. A Snapper that is OFF, or that receives no power, passes nothing. When you snap your fingers, every Snapper that is receiving power at that instant flips between ON and OFF.

I bought $N$ Snappers and chained them together. The first one goes into a wall socket, the second one into the output socket of the first one, and the rest follow the same way. The light is plugged into the $N$th Snapper.

All Snappers start OFF, so only the first one receives power and the light is off. One snap turns Snapper 1 ON and power reaches Snapper 2. Two snaps flip both of them, so Snapper 1 goes OFF and the power to Snapper 2 is cut, but Snapper 2 has already flipped to ON and stays ON with no power. Three snaps turn Snapper 1 back ON and power reaches Snapper 2 again. Both are ON now, so a light plugged into Snapper 2 is on.

After $K$ snaps, is the light on or off? The light is on if and only if it receives power from the Snapper it is plugged into.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $N$ and $K$, separated by a space.

• $1 \le T \le 10000$
• $1 \le N \le 30$
• $0 \le K \le 10^8$

For each test case, print one line in the form "Case #x: y". Here x is the test case number starting from 1, and y is ON if the light is on and OFF if it is off.