스내퍼 사슬 (Large)

스내퍼는 한쪽에 입력 플러그가, 반대쪽에 출력 소켓이 달린 작은 전기 장치다. 출력 소켓에는 전구 같은 전기 제품을 꽂을 수도 있고, 다른 스내퍼의 입력 플러그를 꽂을 수도 있다.

스내퍼의 상태는 ON 또는 OFF다. 상태가 ON이면서 입력 플러그로 전력을 받고 있을 때만 출력 소켓으로 전력이 나간다. 손가락을 튕겨 딱 소리를 내면 그 소리에 반응해서, 그 순간 전력을 받고 있던 스내퍼는 모두 ON과 OFF가 뒤바뀐다.

어느 날 나는 스내퍼 $N$개를 사 와서, 첫 번째 스내퍼의 입력 플러그를 전원 소켓에 꽂고, 두 번째 스내퍼의 입력 플러그를 첫 번째 스내퍼의 출력 소켓에 꽂는 식으로 줄줄이 이어 붙였다. 그리고 $N$번째 스내퍼의 출력 소켓에 전구를 달았다.

처음에는 모든 스내퍼가 OFF이고 첫 번째 스내퍼만 전력을 받으며, 전구는 꺼져 있다. 손가락을 한 번 튕기면 첫 번째 스내퍼가 ON이 되어 두 번째 스내퍼에 전력이 간다. 한 번 더 튕기면 첫 번째와 두 번째 스내퍼의 상태가 함께 바뀌어서, 두 번째 스내퍼는 ON이지만 전력을 받지 못하는 상태가 된다. 세 번째로 튕기면 첫 번째 스내퍼의 상태만 바뀌어 첫 번째와 두 번째가 모두 ON이 된다. 이때 두 번째 스내퍼의 출력 소켓에 전구가 달려 있었다면 전구가 켜진다.

나는 몇 시간이나 손가락을 계속 튕겼다. 손가락을 $K$번 튕긴 뒤, 전구는 켜져 있을까? 전구에는 아무런 장치도 없어서 바로 앞 스내퍼에서 전력을 받을 때만 빛난다.

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

제약 조건

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

각 테스트 케이스마다 한 줄씩 Case #X: Y 형식으로 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 손가락을 $K$번 튕긴 뒤 전구가 켜져 있으면 ON, 꺼져 있으면 OFF다.