Để phạt tính nghịch ngợm, Dante bị nhốt trong một ngôi nhà kỳ lạ có rất nhiều phòng. Ngôi nhà là một lưới phòng \(N\times N\), trong đó \(N\) là số lẻ lớn hơn \(1\). Phòng góc trên bên trái mang số \(1\); các phòng còn lại được đánh số \(2,3,\ldots,N^2\) theo hình xoắn ốc thuận chiều kim đồng hồ. Cụ thể, việc đánh số đi dọc hàng trên cùng, rồi rẽ phải \(90\) độ mỗi khi gặp biên lưới hoặc một phòng đã được đánh số, và kết thúc tại phòng trung tâm. Vì \(N\) lẻ, ngôi nhà luôn có đúng một phòng ở chính giữa và phòng đó luôn mang số \(N^2\).

Chẳng hạn, dưới đây là cách đánh số cho các ngôi nhà có \(N=3\) và \(N=5\).

Dante bắt đầu ở phòng \(1\) và muốn tới phòng trung tâm, tức phòng \(N^2\). Trong suốt hành trình, cậu chỉ có thể đi từ phòng hiện tại sang một phòng kề cạnh có số lớn hơn. Hai phòng chỉ được xem là kề nhau nếu chung một cạnh, không phải chỉ chung một góc.

Dante biết mình có thể đi theo thứ tự số liên tiếp: đang ở phòng \(x\) thì sang \(x+1\), rồi tiếp tục như vậy. Cách đó cần đúng \(N^2-1\) bước. Nhưng Dante muốn làm theo cách riêng: cậu muốn tới phòng trung tâm trong đúng \(K\) bước, với \(K<N^2-1\).

Dante có thể đạt được điều này bằng cách dùng một hoặc nhiều đường tắt. Đường tắt là một bước đi giữa hai phòng không mang số liên tiếp.

Trong ngôi nhà \(5\times5\) ở trên:

• Từ phòng \(1\), Dante không thể sang \(17\), nhưng có thể sang \(2\) hoặc \(16\). Bước sang \(2\) không phải đường tắt vì \(1+1=2\); bước sang \(16\) là đường tắt vì \(1+1\ne16\).
• Từ phòng \(2\), có thể sang \(3\) (không phải đường tắt) hoặc \(17\) (đường tắt), nhưng không thể sang \(1\), \(16\) hay \(18\).
• Từ phòng \(24\), Dante chỉ có thể sang \(25\), và đó không phải đường tắt.
• Không thể đi ra khỏi phòng \(25\).

Xét ví dụ cụ thể trong ngôi nhà \(5\times5\) với \(K=4\). Dante có thể đi \(1\to2\), rồi \(2\to17\) bằng một đường tắt, tiếp theo \(17\to18\), và cuối cùng \(18\to25\) bằng một đường tắt khác. Hình dưới minh họa hành trình; các mũi tên đỏ là đường tắt.

Hãy giúp Dante tìm một dãy đúng \(K\) bước để tới phòng trung tâm, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa hai số nguyên \(N,K\), trong đó \(N\) là kích thước ngôi nhà, tức số hàng và cũng là số cột, còn \(K\) là số bước chính xác Dante muốn đi từ phòng \(1\) tới phòng \(N^2\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\).

Nếu không có dãy đúng \(K\) bước hợp lệ tới phòng trung tâm, \(y\) phải là IMPOSSIBLE.

Nếu có, \(y\) là số lần Dante dùng đường tắt. Vì Dante muốn kết thúc trong ít hơn \(N^2-1\) bước nên luôn phải dùng ít nhất một đường tắt. Sau đó, in thêm \(y\) dòng, mỗi dòng gồm hai số nguyên. Dòng thứ \(i\) biểu diễn lần thứ \(i\) Dante dùng đường tắt trong hành trình, tức đi từ phòng \(a_i\) sang phòng \(b_i\) sao cho \(a_i+1<b_i\).

Các dòng theo đúng thứ tự hành trình, nên \(a_i<a_{i+1}\) với mọi \(1\le i<y\).

Ràng buộc

• \(1\le T\le100\).
• \(1\le K<N^2-1\).
• \(N\bmod2\equiv1\), tức \(N\) lẻ.

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(3\le N\le9\).
• Test Set 2 (phán quyết hiển thị): \(3\le N\le39\).
• Test Set 3 (phán quyết ẩn): \(3\le N\le9999\).

Đ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
5 4
5 3
5 12
3 1

Case #1: 2
2 17
18 25
Case #2: IMPOSSIBLE
Case #3: 2
11 22
22 25
Case #4: IMPOSSIBLE

Nguồn

Google Code Jam 2022, Vòng 2, bài Spiraling Into Control.

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