题目描述

给定 $n$ 个字符串 $s_1, s_2, \dots, s_n$，每个字符串的长度不超过 $8$。

对于每个字符串 $s_i$，判断是否存在两个字符串 $s_j$ 和 $s_k$，使得 $s_i = s_j + s_k$，即 $s_i$ 是 $s_j$ 和 $s_k$ 的拼接。注意，$j$ 可以等于 $k$。

回忆一下，字符串 $s$ 和 $t$ 的拼接定义为 $s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$，其中 $p$ 和 $q$ 分别是 $s$ 和 $t$ 的长度。例如，"code" 和 "forces" 的拼接是 "codeforces"。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示字符串的数量。

接下来 $n$ 行，每行一个非空字符串 $s_i$，长度不超过 $8$，仅包含小写英文字母。给定的 $n$ 个字符串中可能有重复。

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

输出格式

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串。第 $i$ 位为 $\texttt{1}$ 表示存在 $s_j$ 和 $s_k$ 使得 $s_i = s_j + s_k$，否则为 $\texttt{0}$。注意，$j$ 可以等于 $k$。

说明/提示

在第一个测试用例中，有如下情况：

• $s_1 = s_2 + s_2$，因为 $\texttt{abab} = \texttt{ab} + \texttt{ab}$。注意 $j$ 可以等于 $k$。
• $s_2$ 不是列表中任意两个字符串的拼接。
• $s_3 = s_2 + s_5$，因为 $\texttt{abc} = \texttt{ab} + \texttt{c}$。
• $s_4$ 不是列表中任意两个字符串的拼接。
• $s_5$ 不是列表中任意两个字符串的拼接。

因此，只有 $s_1$ 和 $s_3$ 满足条件，所以答案为 $\texttt{10100}$。

由 ChatGPT 4.1 翻译

样例

3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code

10100
011
10100101