眾所周知,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