#P17899. Challenge Matrix Multiplication II

Challenge Matrix Multiplication II

给定整数 xx,请构造一个无向、无权、连通的简单图。图中有 nn 个顶点,编号为 1,…,n1,\ldots,n,且 2≤n≤852\le n\le85。

设 dist⁡(i,j)\operatorname{dist}(i,j) 为顶点 ii 到 jj 的最短路长度(每条边长度均为 11)。你构造的图必须满足

∑1≤i<j≤ndist⁡(i,j)=x.\sum_{1\le i<j\le n}\operatorname{dist}(i,j)=x.

输入格式

第一行是测试组数 TT,1≤T≤20001\le T\le2000。

接下来 TT 行,每行给出一个整数 xx,1≤x≤1051\le x\le10^5。输入保证存在满足顶点数限制的解。

输出格式

对每组数据,先输出顶点数 nn,然后输出 n−1n-1 个二进制字符串。

第 ii 个字符串的长度必须为 n−in-i。它的第 jj 个字符为 1 表示存在边 (i,i+j)(i,i+j),为 0 表示不存在这条边。这里 i,ji,j 均从 11 开始。

可以输出任意满足要求的图。

样例 1

输入

4
1
3
6
8

输出

2
1
3
11
1
4
111
11
1
4
110
10
1