스내퍼 사슬 (큰 입력)

스내퍼는 한쪽에 입력 플러그가 있고 반대쪽에 출력 소켓이 달린 작은 장치다. 입력 플러그를 아무 출력 소켓에나 꽂고, 스내퍼의 출력 소켓에는 전등이나 다른 장치를 꽂는다.

켜짐 상태이면서 전원을 받고 있는 스내퍼는 출력 소켓에 꽂힌 장치로 전원을 그대로 보낸다. 꺼짐 상태인 스내퍼나 전원을 받지 못하는 스내퍼는 아무것도 보내지 않는다. 손가락을 한 번 튕기면 그 순간 전원을 받고 있던 스내퍼가 모두 켜짐과 꺼짐 사이로 뒤집힌다.

나는 스내퍼 $N$개를 사서 사슬처럼 이었다. 첫 번째는 벽 소켓에, 두 번째는 첫 번째 스내퍼의 출력 소켓에, 나머지도 같은 방식으로 꽂았다. 전등은 $N$번째 스내퍼에 꽂혀 있다.

처음에는 모든 스내퍼가 꺼짐 상태라 첫 번째만 전원을 받고 전등은 꺼져 있다. 손가락을 한 번 튕기면 1번 스내퍼가 켜지고 2번 스내퍼에 전원이 들어간다. 두 번 튕기면 둘 다 뒤집혀 1번이 꺼지고 2번으로 가는 전원이 끊기지만, 2번은 이미 켜짐으로 바뀐 뒤라 전원 없이 켜짐 상태로 남는다. 세 번 튕기면 1번이 다시 켜지면서 2번에 전원이 들어간다. 이제 둘 다 켜짐이므로 2번 스내퍼에 꽂은 전등은 켜진다.

손가락을 $K$번 튕긴 뒤 전등은 켜져 있는가, 꺼져 있는가? 전등은 자신이 꽂힌 스내퍼에서 전원을 받을 때만 켜진다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다.

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

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 전등이 켜져 있으면 ON, 꺼져 있으면 OFF다.