CF1514E.Baby Ehab's Hyper Apartment

This is an interactive problem.

Baby Ehab loves crawling around his apartment. It has $n$ rooms numbered from $0$ to $n-1$. For every pair of rooms, $a$ and $b$, there's either a direct passage from room $a$ to room $b$, or from room $b$ to room $a$, but never both.

Baby Ehab wants to go play with Baby Badawy. He wants to know if he could get to him. However, he doesn't know anything about his apartment except the number of rooms. He can ask the baby sitter two types of questions:

• is the passage between room $a$ and room $b$ directed from $a$ to $b$ or the other way around?
• does room $x$ have a passage towards any of the rooms $s_1$, $s_2$, ..., $s_k$?

He can ask at most $9n$ queries of the first type and at most $2n$ queries of the second type.

After asking some questions, he wants to know for every pair of rooms $a$ and $b$ whether there's a path from $a$ to $b$ or not. A path from $a$ to $b$ is a sequence of passages that starts from room $a$ and ends at room $b$.

这是一个交互式问题。

宝宝 Ehab 喜欢在他家的公寓里爬来爬去。公寓共有 $n$ 个房间，编号从 $0$ 到 $n-1$。对于任意两个房间 $a$ 和 $b$，要么存在一条从房间 $a$ 指向房间 $b$ 的单向通道，要么存在一条从房间 $b$ 指向房间 $a$ 的单向通道，但二者不会同时存在。

宝宝 Ehab 想去找宝宝 Badawy 一起玩。他想知道能否从自己所在房间到达宝宝 Badawy 所在房间。然而，他对公寓结构一无所知，只知道房间总数 $n$。他可以向保姆提出两类问题：

• 房间 $a$ 与房间 $b$ 之间的通道方向是从 $a$ 指向 $b$，还是从 $b$ 指向 $a$？
• 房间 $x$ 是否存在指向房间 $s_1, s_2, \dots, s_k$ 中任意一个房间的通道？

他最多可提出 $9n$ 个第一类问题，以及最多 $2n$ 个第二类问题。

在提出若干问题后，他需要确定：对每一对房间 $a$ 和 $b$，是否存在一条从 $a$ 到 $b$ 的路径。所谓从 $a$ 到 $b$ 的路径，是指由若干条通道构成的一个序列，该序列起始于房间 $a$，终止于房间 $b$。

The first line contains an integer $t$ ($1 \le t \le 30$) — the number of test cases you need to solve.

Then each test case starts with an integer $n$ ($4 \le n \le 100$) — the number of rooms.

The sum of $n$ across the test cases doesn't exceed $500$.

第一行包含一个整数 $t$（$1 \le t \le 30$）—— 表示你需要求解的测试用例数量。

接下来，每个测试用例以一个整数 $n$（$4 \le n \le 100$）开始 —— 表示房间的数量。

所有测试用例中 $n$ 的总和不超过 $500$。

To print the answer for a test case, print a line containing "3", followed by $n$ lines, each containing a binary string of length $n$. The $j$-th character of the $i$-th string should be $1$ if there's a path from room $i$ to room $j$, and $0$ if there isn't. The $i$-th character of the $i$-th string should be $1$ for each valid $i$.

After printing the answer, we will respond with a single integer. If it's $1$, you printed a correct answer and should keep solving the test cases (or exit if it is the last one). If it's $-1$, you printed a wrong answer and should terminate to get Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

对于每个测试用例，输出答案时，请先输出一行包含字符 "3"，然后输出 $n$ 行，每行是一个长度为 $n$ 的二进制字符串。其中第 $i$ 行的第 $j$ 个字符应为 $1$ 当且仅当存在一条从房间 $i$ 到房间 $j$ 的路径；否则为 $0$。对每个合法的 $i$，第 $i$ 行的第 $i$ 个字符必须为 $1$。

输出答案后，系统将返回一个整数：若该整数为 $1$，说明你输出了正确答案，此时应继续处理后续测试用例（若已无更多测试用例，则可退出）；若该整数为 $-1$，说明你输出了错误答案，此时应立即终止程序以获得 “Wrong answer” 判定；否则，由于你的程序将继续从已关闭的输入流中读取数据，你可能会得到任意判定。

In the given example:

The first query asks whether there's a passage from room $3$ to any of the other rooms.

The second query asks about the direction of the passage between rooms $0$ and $1$.

After a couple other queries, we concluded that you can go from any room to any other room except if you start at room $3$, and you can't get out of this room, so we printed the matrix:

1111
1111
1111
0001

The interactor answered with $1$, telling us the answer is correct.

在给定的例子中：

第一个查询询问：是否存在一条从房间 $3$ 到其余任意一个房间的通路。

第二个查询询问：房间 $0$ 与房间 $1$ 之间的通路方向。

在进行若干次其他查询后，我们得出结论：除从房间 $3$ 出发的情形外，任意房间均可到达其余任意房间；而一旦位于房间 $3$，便无法离开该房间。因此我们输出了如下矩阵：

1111
1111
1111
0001

交互器返回 $1$，表示该答案正确。