Bạn quá hào hứng với Vòng chung kết Code Jam Thế giới 2016 nên vừa chuyển tới New York. Bạn mang theo \(J\) chiếc áo khoác khác nhau (đánh số từ 1 đến \(J\)), \(P\) chiếc quần khác nhau (đánh số từ 1 đến \(P\)), và \(S\) chiếc áo sơ mi khác nhau (đánh số từ 1 đến \(S\)). Số áo sơ mi không ít hơn số quần, và số quần không ít hơn số áo khoác: \(J\le P\le S\).

Mỗi ngày, bạn chọn một áo khoác, một quần và một áo sơ mi để tạo thành một bộ trang phục. Mỗi tối bạn giặt tất cả quần áo, nên hôm sau món nào cũng có thể dùng lại.

Ở New York, Cảnh sát Thời trang luôn theo dõi và ghi lại trang phục hằng ngày của mọi người. Nếu phát hiện bạn mặc cùng một bộ trang phục chính xác hai lần, họ sẽ lập tức đưa bạn tới Nhà tù Thời trang trên Đại lộ 5 để bắt buộc thay đổi phong cách; bạn chắc chắn muốn tránh điều đó! Bạn cũng bị đưa đi ngay nếu họ phát hiện cùng một cặp hai món đồ đã được mặc tổng cộng quá \(K\) lần. Một cặp có thể là một áo khoác cụ thể với một quần cụ thể, một áo khoác cụ thể với một áo sơ mi cụ thể, hoặc một quần cụ thể với một áo sơ mi cụ thể. Ví dụ, trong hai bộ (áo khoác 1, quần 2, áo sơ mi 3) và (áo khoác 1, quần 1, áo sơ mi 3), cặp (áo khoác 1, áo sơ mi 3) xuất hiện hai lần, còn cặp (quần 1, áo sơ mi 3) chỉ xuất hiện một lần.

Bạn mặc một bộ mỗi ngày. Hãy tìm số ngày lớn nhất có thể tránh Nhà tù Thời trang và đưa ra danh sách trang phục dùng cho từng ngày.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa bốn số nguyên \(J,P,S,K\).

Dữ liệu ra

Với mỗi bộ test, trước tiên in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số ngày lớn nhất bạn có thể tránh bị đưa tới Nhà tù Thời trang. Sau đó in thêm \(y\) dòng, mỗi dòng gồm ba số nguyên: số hiệu áo khoác, quần và áo sơ mi, theo thứ tự đó, tạo thành trang phục của một ngày. Danh sách có thể theo bất kỳ thứ tự nào, nhưng không được gây ra vi phạm nào đã mô tả.

Nếu có nhiều đáp án, bạn có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le J \le P \le S\).
• \(1 \le K \le 10\).

Phân nhóm

• Test Set 1 (Hiển thị): \(S\le3\).
• Test Set 2 (Ẩn): \(S\le10\).

Đ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 1 1 10
1 2 3 2
1 1 3 2
1 2 3 1

Case #1: 1
1 1 1
Case #2: 4
1 1 2
1 2 3
1 2 1
1 1 1
Case #3: 2
1 1 2
1 1 1
Case #4: 2
1 1 3
1 2 1

1 2 2
1 1 1

Nguồn

Google Code Jam 2016, Vòng 1C, bài Fashion Police.

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