Snapper là một thiết bị nhỏ thông minh, một đầu cắm vào ổ cắm điện (hoặc ổ cắm đầu ra của một Snapper khác), và đầu kia cung cấp một ổ cắm đầu ra để cắm đèn hoặc các thiết bị khác.

Khi một Snapper ở trạng thái BẬT (ON) và đang nhận được điện từ phích cắm đầu vào của nó, thì thiết bị kết nối với ổ cắm đầu ra của nó cũng sẽ nhận được điện. Khi bạn búng tay -- tạo ra một tiếng "tách" -- bất kỳ Snapper nào đang nhận được điện tại thời điểm búng tay sẽ chuyển đổi trạng thái giữa BẬT (ON) và TẮT (OFF).

Với hy vọng phá hủy vũ trụ bằng một điểm kỳ dị, tôi đã mua \(N\) thiết bị Snapper và xâu chuỗi chúng lại với nhau bằng cách cắm thiết bị đầu tiên vào ổ cắm điện, thiết bị thứ hai vào thiết bị đầu tiên, và cứ tiếp tục như vậy. Đèn được cắm vào thiết bị Snapper thứ \(N\).

Ban đầu, tất cả các Snapper đều ở trạng thái TẮT, vì vậy chỉ có thiết bị đầu tiên nhận được điện từ ổ cắm, và đèn tắt. Tôi búng tay một lần, làm thiết bị Snapper đầu tiên chuyển sang trạng thái BẬT và truyền điện cho thiết bị thứ hai. Tôi búng tay lần thứ hai, làm cả hai thiết bị Snapper chuyển trạng thái và sau đó ngay lập tức ngắt điện khỏi thiết bị thứ hai, để lại nó ở trạng thái BẬT nhưng không có điện. Tôi búng tay lần thứ ba, làm thiết bị Snapper đầu tiên chuyển trạng thái một lần nữa và truyền điện cho thiết bị thứ hai. Bây giờ cả hai thiết bị Snapper đều ở trạng thái BẬT, và nếu đèn của tôi được cắm vào thiết bị Snapper thứ hai, nó sẽ sáng.

Tôi tiếp tục làm việc này trong nhiều giờ. Liệu đèn sẽ sáng hay tắt sau khi tôi đã búng tay \(K\) lần? Đèn sáng khi và chỉ khi nó nhận được điện từ thiết bị Snapper mà nó được cắm vào.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(N\) và \(K\).

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là "ON" hoặc "OFF", cho biết trạng thái của bóng đèn.

Ràng buộc

• \(1 \le T \le 10,000\).

Phân nhóm

• Small dataset (Test set 1 - Visible):
• \(1 \le N \le 10\);
• \(0 \le K \le 100\);
• Large dataset (Test set 2 - Hidden):
• \(1 \le N \le 30\);
• \(0 \le K \le 10^8\);

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
1 0
1 1
4 0
4 47

Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON

Nguồn

Google Code Jam 2010, Vòng loại, bài Snapper Chain.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.