Description

一个无向图的生成树，是指在只使用该图已有边的前提下，包含所有 $N$ 个节点、且恰好有 $N-1$ 条边、并且是一棵树的子图。

请你构造一个至少包含 $2$ 个节点、且不超过 $22$ 个节点的图，使得该图恰好有 $K$ 种不同的生成树。（当且仅当两棵生成树所用的边集合不同，这两棵生成树才被认为是不同的。）图中每对节点之间至多有一条边，且不得包含自环（即节点与自身相连的边）。

保证对于下述范围内的每个 $K$，都至少存在一种满足条件的图。

Input Format

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试用例，每组测试用例包含一行，内有一个整数 $K$，表示期望的生成树数量。

Output Format

对于每个测试用例，首先输出一行 Case #x: y，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 表示你构造的图的节点数（$y$ 必须在 $2$ 到 $22$ 之间）。接下来输出 $y$ 行，每行 $y$ 个字符，表示该图的邻接矩阵。第 $i$ 行第 $j$ 列为 $1$，表示第 $i$ 个节点与第 $j$ 个节点之间有一条边；为 $0$，表示没有边。注意，该邻接矩阵是对称的，且主对角线上的元素均为 $0$。

如果存在多种答案，你可以输出任意一种。保证对于下述范围内的每个 $K$，都至少存在一种合法解。

2
3
8

Case #1: 3
011
101
110
Case #2: 4
0111
1001
1001
1110

Hint

样例解释

在第 1 个用例中，图是一个三角形，去掉任意一条边都能得到一棵不同的生成树。

在第 2 个用例中，解中的可用边为 $1-2$、$1-3$、$1-4$、$2-4$ 和 $3-4$。这 8 棵不同的生成树分别由如下边集定义：

• $1-2$、$1-3$、$1-4$
• $1-2$、$1-3$、$2-4$
• $1-2$、$1-3$、$3-4$
• $1-2$、$1-4$、$3-4$
• $1-2$、$2-4$、$3-4$
• $1-3$、$1-4$、$2-4$
• $1-3$、$2-4$、$3-4$
• $1-4$、$2-4$、$3-4$

限制条件

• $1 \leqslant T \leqslant 300$。

小数据集（30 分，测试集 1 - 可见）

• $3 \leqslant K \leqslant 10000$。

翻译由 GPT4.1 完成。