眾所周知,APSP(全點對最短路徑)問題與 min+ 矩陣乘法有著深刻的聯繫。今天,我們希望你解決以下問題:
給定 $x$,構造一個無向無權連通圖(即所有邊權均為 1),使得 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$。這裡,$\operatorname{dis}(i, j)$ 表示節點 $i$ 與節點 $j$ 之間的最短路徑長度。
這個問題當然非常簡單……不幸的是,你的資源有限,因此你希望找到一個節點數不超過 85 且滿足要求的圖。
輸入格式
單個測試資料包含多組資料集。
輸入的第一行是資料集的數量 $T$ ($1 \le T \le 2000$),表示該測試資料中包含的資料集數量。
對於每組資料集,有一行包含一個整數 $x$ ($1 \le x \le 10^5$),表示需要滿足的限制條件。保證存在至少一個節點數不超過 85 的圖滿足條件。
輸出格式
對於每組資料集,在第一行輸出你使用的節點數 $n$ ($2 \le n \le 85$)。接著輸出 $n - 1$ 行,其中第 $i$ 行是一個長度為 $n - i$ 的二進位字串。第 $i$ 行的第 $j$ 個字元為 1 若且唯若節點 $i$ 與節點 $i + j$ 之間存在一條邊。
範例
輸入
4 1 3 6 8
輸出
2 1 3 11 1 4 111 11 1 4 110 10 1