Trong giờ giải lao trên lớp, Alice nghĩ ra một trò chơi để đố Bob. Alice vẽ ra giấy trắng một bảng kích thước ~8 \times 8~, các hàng được đánh số từ ~1~ đến ~8~ từ trên xuống dưới, và các cột được đánh số từ ~1~ đến ~8~ từ trái sang phải. Alice đã bí mật tô một số ô thành màu đen, các ô còn lại là màu trắng. Biết rằng số ô màu đen nhiều hơn số ô màu trắng. Alice yêu cầu Bob cần phải tìm ra một tập ~5~ ô đen sao cho nếu đặt ~5~ quân xe vào đó thì: không có hai quân xe nào nằm cùng hàng hoặc cùng cột.

Bob không được nhìn bảng; thay vào đó, Bob được phép hỏi nhiều lần Alice: trong một tập các ô có bao nhiêu ô trong đó là màu đen. Alice luôn trả lời đúng theo cấu hình bí mật. Vì giờ giải lao rất ngắn nên Bob cần phải đặt càng ít câu hỏi càng tốt để tìm ra một tập ~5~ ô đen hợp lệ.

Input

Dòng đầu chứa số nguyên dương ~T~ (~1 \le T \le 100~) - số trường hợp test. Dưới đây là mô tả của các trường hợp test.

Tương tác

Để thực hiện phép hỏi, bạn cần chọn ra ~k~ cặp số nguyên ~(r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)~ là toạ độ của các ô trong tập các ô cần hỏi và in ra luồng dữ liệu chuẩn một dòng dưới dạng sau:

• "? ~k~ ~r_1~ ~c_1~ ~r_2~ ~c_2~ ~\dots~ ~r_k~ ~c_k~".

Ngay sau đó bạn đọc từ luồng dữ liệu chuẩn một số nguyên là số lượng ô màu đen trong tập ô đã chọn.

Khi đã tìm được ~5~ ô đen có toạ độ ~(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5)~ theo yêu cầu, bạn in ra luồng dữ liệu chuẩn một dòng dưới dạng sau:

• "! ~x_1~ ~y_1~ ~x_2~ ~y_2~ ~x_3~ ~y_3~ ~x_4~ ~y_4~ ~x_5~ ~y_5~".

Sau khi in ra, đừng quên xuất ký tự xuống dòng (end of line) và làm sạch bộ đệm đầu ra (flush the output). Nếu không, bạn sẽ gặp lỗi. Để làm điều này, hãy sử dụng:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• flush(output) trong Pascal;
• stdout.flush() trong Python;
• Download file sau để hình dung cách tương tác.

Chấm điểm

Với mỗi test, nếu bạn trả lời đúng tập các điểm cần tìm, gọi ~Q~ là số lần thực hiện phép hỏi lớn nhất trong toàn bộ các trường hợp test. Điểm cho mỗi test được tính như sau:

• ~0~ điểm nếu ~Q > 64~;
• ~100\%~ số điểm nếu ~Q \le 9~;
• Ngược lại bạn nhận được ~0.9 - (Q - 9) \times 0.01~.

Ràng buộc:

• Subtask 1 (~30~ điểm): Có đúng ~5~ ô được tô màu đen trong số các ô trên đường chéo chính (các ô có chỉ số hàng bằng chỉ số cột).
• Subtask 2 (~70~ điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

1

2

0

3

Output

? 3 1 1 2 2 3 3

? 1 3 3

? 3 4 4 5 5 6 6

! 1 1 2 2 4 4 5 5 6 6

Xét một bảng kích thước ~n~ dòng, ~n~ cột chứa các ô trống và các số tự nhiên ~1~ hoặc ~2~. Bảng số được gọi là đẹp nếu như nó có các tính chất:

• Mỗi hàng và mỗi cột chứa đúng một số ~1~, một số ~2~ và ~n-2~ số ô trống.
• Bắt đầu từ góc trên cùng bên trái, bắt đầu di chuyển sang phải rồi theo hình xoắn ốc vào trong, các giá trị ở các ô chứa số sẽ xuất hiện theo thứ tự ~1~, ~2~, ~1~, ~2~, ...

Hình dưới đây là ví dụ về một bảng số đẹp kích thước ~4 \times 4~:

Yêu cầu

Cho một số tự nhiên ~n~, bạn hãy tạo ra một bảng đẹp kích thước ~n\times n~

Dữ liệu

Vào từ thiết bị nhập chuẩn một số tự nhiên ~n~ duy nhất trên một dòng (~2\le n\le 200~).

Kết quả

• Nếu có lời giải, ghi ra ~n~ dòng, mỗi dòng có ~n~ số được phân tách bằng một dấu cách, biểu diễn bảng được yêu cầu, trong đó ô trống được ghi bởi số ~0~.
• Nếu không có lời giải, hãy ghi giá trị ~-1~ trên một dòng duy nhất

Nếu có nhiều lời giải, bạn có thể in ra bất kỳ lời giải nào đúng.

Ví dụ

Ràng buộc

• Subtask 1 (~50\%~ số điểm): ~n \leq 15~
• Subtask 2 (~50\%~ số điểm): Không có ràng buộc bổ sung

Xét một bảng kích thước ~n~ dòng, ~n~ cột chứa các ô trống và các số tự nhiên trong khoảng từ 1 đến ~k~ (~k \le n~). Bảng số được gọi là k-đẹp nếu như nó có các tính chất:

• Mỗi hàng và mỗi cột chứa đúng ~n~ – ~k~ số ô trống.
• Trên mỗi hàng và mỗi cột, mỗi số ~x~ (~1 \leq x \leq k~) xuất hiện đúng một lần.
• Bắt đầu từ góc trên cùng bên trái, bắt đầu di chuyển sang phải rồi theo hình xoắn ốc vào trong, các giá trị ở các ô chứa số sẽ xuất hiện theo thứ tự 1, 2, ..., ~k~, 1, 2, ..., ~k~, ...

Hình dưới đây là ví dụ về một bảng số 2-đẹp kích thước 4x4:

Yêu cầu

Cho số tự nhiên ~n~ và ~k~, bạn hãy tạo ra một bảng k-đẹp kích thước ~n\times n~

Dữ liệu:

Vào từ thiết bị nhập chuẩn hai số tự nhiên ~n~ và ~k~ duy nhất trên một dòng (~2\le n\le 200~, ~2 \le k \le \min(n, 3)~)

Kết quả:

• Nếu có lời giải, ghi ra ~n~ dòng, mỗi dòng có ~n~ số được phân tách bằng một dấu cách, biểu diễn bảng được yêu cầu, trong đó ô trống được ghi bởi số 0.
• Nếu không có lời giải, hãy ghi giá trị – 1 trên một dòng duy nhất. Nếu có nhiều lời giải, bạn có thể in ra bất kỳ lời giải nào đúng.

Ví dụ

Ràng buộc

• Subtask 1 (~40\%~ số điểm): ~k = 2~
• Subtask 2 (~60\%~ số điểm): ~k = 3~