Như đã biết, bài toán APSP (Đường đi ngắn nhất giữa mọi cặp đỉnh) có mối liên hệ sâu sắc với phép nhân ma trận min+. Hôm nay, chúng tôi muốn bạn giải quyết bài toán sau:
Cho $x$, hãy dựng một đồ thị vô hướng không trọng số liên thông (tức là mọi cạnh đều có trọng số bằng 1) sao cho $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. Ở đây, $\operatorname{dis}(i, j)$ biểu thị độ dài đường đi ngắn nhất giữa đỉnh $i$ và đỉnh $j$.
Bài toán này tất nhiên rất đơn giản... Đáng tiếc là tài nguyên của bạn có hạn, vì vậy bạn mong muốn tìm được một đồ thị có không quá 85 đỉnh thỏa mãn yêu cầu.
Dữ liệu vào
Một bộ kiểm tra duy nhất chứa nhiều bộ dữ liệu.
Dòng đầu tiên của dữ liệu vào là số lượng bộ dữ liệu $T$ ($1 \le T \le 2000$), biểu thị số bộ dữ liệu có trong bộ kiểm tra này.
Với mỗi bộ dữ liệu, có một dòng chứa một số nguyên $x$ ($1 \le x \le 10^5$), biểu thị ràng buộc cần thỏa mãn. Đảm bảo tồn tại ít nhất một đồ thị có không quá 85 đỉnh thỏa mãn điều kiện.
Kết quả
Với mỗi bộ dữ liệu, in ra số đỉnh $n$ mà bạn đã sử dụng trên dòng đầu tiên ($2 \le n \le 85$). Sau đó in ra $n - 1$ dòng, trong đó dòng thứ $i$ là một xâu nhị phân độ dài $n - i$. Ký tự thứ $j$ của dòng thứ $i$ là 1 khi và chỉ khi có cạnh nối giữa đỉnh $i$ và đỉnh $i + j$.
Ví dụ
Dữ liệu vào
4 1 3 6 8
Kết quả
2 1 3 11 1 4 111 11 1 4 110 10 1