Snapper 체인

Snapper는 영리하고 작은 장치이다. 한쪽에서는 입력 플러그를 출력 소켓에 꽂고, 다른 쪽에는 조명이나 다른 장치를 연결할 수 있는 출력 소켓이 나와 있다.

Snapper가 ON 상태이고 입력 플러그로부터 전력을 공급받고 있으면, 출력 소켓에 연결된 장치에도 전력이 공급된다. 손가락을 튕겨 딸깍 소리를 내면, 그 순간 전력을 공급받고 있는 모든 Snapper가 ON 상태와 OFF 상태 사이에서 전환된다.

특이점을 이용해 우주를 파괴하려는 희망으로, 나는 Snapper 장치 N개를 구매하여 첫 번째 장치를 전원 소켓에 꽂고, 두 번째 장치를 첫 번째 장치에 꽂는 식으로 서로 연결했다. 조명은 N번째 Snapper에 연결되어 있다.

처음에는 모든 Snapper가 OFF 상태이므로 첫 번째 장치만 소켓에서 전력을 공급받고, 조명은 꺼져 있다. 손가락을 한 번 튕기면 첫 번째 Snapper가 ON 상태로 전환되어 두 번째 장치에 전력을 공급한다. 손가락을 다시 튕기면 두 Snapper가 모두 전환된 다음 두 번째 장치의 전력이 즉시 끊기므로, 두 번째 장치는 ON 상태이지만 전력은 공급받지 못한다. 손가락을 세 번째로 튕기면 첫 번째 Snapper가 다시 전환되어 두 번째 장치에 전력을 공급한다. 이제 두 Snapper가 모두 ON 상태이며, 조명을 두 번째 Snapper에 연결했다면 조명이 켜진다.

나는 몇 시간 동안 이 일을 계속한다. 손가락을 K번 튕긴 뒤 조명은 켜져 있을까, 꺼져 있을까? 조명은 자신이 연결된 Snapper로부터 전력을 공급받을 때, 그리고 그럴 때에만 켜져 있다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 10,000.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 10; 0 ≤ K ≤ 100;

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 30; 0 ≤ K ≤ $10^{8}$;

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 두 정수 N과 K가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 조명의 상태를 나타내는 "ON" 또는 "OFF"이다.