Snapper Chain (Large)

A snapper is a small electrical device with an input plug on one side and an output socket on the other. You can plug an appliance such as a light bulb into the output socket, or the input plug of another snapper.

A snapper is either ON or OFF. Power leaves the output socket only when the snapper is ON and its input plug is receiving power. When you snap your fingers, every snapper that is receiving power at that moment reacts to the sound and flips between ON and OFF.

One day I bought $N$ snappers. I plugged the input plug of the first snapper into a power socket, plugged the input plug of the second snapper into the output socket of the first, and continued that way down the chain. Then I attached a light bulb to the output socket of the $N$th snapper.

At the start every snapper is OFF, only the first snapper receives power, and the bulb is dark. After one snap the first snapper turns ON and power reaches the second snapper. After a second snap the first and second snappers both flip, so the second snapper is ON but receives no power. On the third snap only the first snapper flips, and now the first and second are both ON. If a bulb were attached to the output socket of the second snapper, it would light up.

I kept snapping my fingers for hours. After $K$ snaps, is the bulb lit? The bulb is an ordinary one with no tricks in it, and it shines only while the snapper in front of it supplies power.

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.

Constraints

• $1 \le T \le 5000$
• $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 bulb is lit after $K$ snaps and OFF otherwise.