잘 알려져 있듯이, APSP(모든 쌍 최단 경로) 문제는 min+ 행렬 곱셈과 깊은 관련이 있습니다. 오늘 여러분이 해결해야 할 문제는 다음과 같습니다.
$x$가 주어졌을 때, $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$를 만족하는 무방향 비가중치 연결 그래프(즉, 모든 간선의 가중치가 1인 그래프)를 구성하세요. 여기서 $\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$번째 문자는 정점 $i$와 정점 $i + j$ 사이에 간선이 존재할 때만 1입니다.
예제
입력
4 1 3 6 8
출력
2 1 3 11 1 4 111 11 1 4 110 10 1