Cây khung của một đồ thị vô hướng có \(N\) đỉnh là một cây gồm \(N-1\) cạnh, chỉ sử dụng các cạnh của đồ thị và chứa đủ cả \(N\) đỉnh.

Hãy xây dựng một đồ thị có ít nhất 2 và không quá 22 đỉnh sao cho đồ thị có đúng \(K\) cây khung khác nhau. Hai cây khung được coi là khác nhau khi và chỉ khi tập cạnh của chúng khác nhau.

Đồ thị phải là đồ thị đơn: giữa mỗi cặp đỉnh có nhiều nhất một cạnh và không được có khuyên, tức cạnh nối một đỉnh với chính nó.

Với mọi \(K\) trong giới hạn bên dưới, đề bài bảo đảm tồn tại ít nhất một đồ thị thỏa mãn.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\).

Mỗi test gồm một dòng chứa số nguyên \(K\): số cây khung mong muốn.

Dữ liệu ra

Với mỗi test, trước tiên in một dòng có dạng Case #x: y, trong đó x là số thứ tự test, bắt đầu từ 1, và \(y\) là số đỉnh của đồ thị được xây dựng. Giá trị \(y\) phải nằm trong đoạn từ 2 đến 22, kể cả hai đầu.

Sau đó, in thêm \(y\) dòng. Dòng thứ \(i\) trong số này biểu diễn đỉnh thứ \(i\) và phải chứa đúng \(y\) ký tự. Ký tự thứ \(j\) trên dòng thứ \(i\) phải là:

• 1 nếu đỉnh thứ \(i\) và đỉnh thứ \(j\) được nối bởi một cạnh;
• 0 nếu không có cạnh như vậy.

Ma trận này phải đối xứng và mọi phần tử trên đường chéo chính phải là 0.

Nếu có nhiều đáp án, có thể in bất kỳ đáp án hợp lệ nào. Đề bài bảo đảm tồn tại đáp án cho mọi \(K\) thuộc giới hạn.

Ràng buộc

• \(1 \le T \le 300\).
• \(3 \le K \le 10000\).
• Bài chỉ có một Test Set và không có Test Set lớn.
• Có thể nộp lại Test Set này; mỗi lần thử lại chịu hình phạt thời gian theo quy định của cuộc thi gốc.

Phân nhóm

• Test Set 1 (Visible): \(3 \le K \le 10000\).

Đ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ụ

2
3
8

Case #1: 3
011
101
110
Case #2: 4
0111
1001
1001
1110

1-2, 1-3, 1-4
1-2, 1-3, 2-4
1-2, 1-3, 3-4
1-2, 1-4, 3-4
1-2, 2-4, 3-4
1-3, 1-4, 2-4
1-3, 2-4, 3-4
1-4, 2-4, 3-4

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Spanning Planning.

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