多字符串（strings）

题目描述

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

对于每个字符串 $s_i$，请判断是否存在两个字符串 $s_j$ 和 $s_k$，使得：

其中 $+$ 表示字符串拼接。

注意：

• $j$ 可以等于 $k$；
• 给定的字符串中可能存在完全相同的字符串；
• 只要能找到任意两个给定字符串拼接成 $s_i$，就认为 $s_i$ 满足条件。

例如，字符串 $\texttt{damo}$ 和 $\texttt{nthrone}$ 拼接后可以得到 $\texttt{damonthrone}$。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$，表示字符串数量。

接下来 $n$ 行，每行包含一个非空字符串 $s_i$。

字符串只包含小写英文字母，且长度不超过 $8$。

输出格式

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串。

如果第 $i$ 个字符串可以由给定字符串中的两个字符串拼接得到，则第 $i$ 位输出 $\text{1}$，否则输出 $\text{0}$。

输入输出样例 #1

输入 #1

2
5
abab
ab
abc
abacb
c
3
x
xx
xxx

输出 #1

10100
011

样例解释 #1

对于第 $1$ 组测试数据：

共有 $5$ 个字符串：

abab
ab
abc
abacb
c

其中：

• $\texttt{abab}$ 可以由 $\texttt{ab} + \texttt{ab}$ 拼接得到，因此输出 $\text{1}$；
• $\texttt{ab}$ 不能由两个给定字符串拼接得到，因此输出 $\text{0}$；
• $\texttt{abc}$ 可以由 $\texttt{ab} + \texttt{c}$ 拼接得到，因此输出 $\text{1}$；
• $\texttt{abacb}$ 不能由两个给定字符串拼接得到，因此输出 $\text{0}$；
• $\texttt{c}$ 不能由两个给定字符串拼接得到，因此输出 $\text{0}$。

所以输出：$\text{10100}$

对于第 $2$ 组测试数据：

共有 $3$ 个字符串：

x
xx
xxx

其中：

• $\texttt{x}$ 不能由两个非空字符串拼接得到，因此输出 $\text{0}$；
• $\texttt{xx}$ 可以由 $\texttt{x} + \texttt{x}$ 拼接得到，因此输出 $\text{1}$；
• $\texttt{xxx}$ 可以由 $\texttt{x} + \texttt{xx}$ 拼接得到，因此输出 $\text{1}$。

所以输出：$\text{011}$

输入输出样例 #2

输入 #2

2
6
a
b
ab
ba
aa
bb
5
damo
nthrone
damonthrone
throne
damon

输出 #2

001111
00100

样例解释 #2

对于第 $1$ 组测试数据：

• $\texttt{ab} = \texttt{a} + \texttt{b}$；
• $\texttt{ba} = \texttt{b} + \texttt{a}$；
• $\texttt{aa} = \texttt{a} + \texttt{a}$；
• $\texttt{bb} = \texttt{b} + \texttt{b}$。

因此输出：$\text{001111}$

对于第 $2$ 组测试数据：

$\texttt{damonthrone}$ 可以由 $\texttt{damo} + \texttt{nthrone}$ 拼接得到，其余字符串都不能由两个给定字符串拼接得到。

因此输出：$\text{00100}$

数据范围与约定

对于所有测试数据，保证：

需要注意 ：$\texttt{damonthrone}$ 只是为了写一下团队名字，虽然长度超过 $8$ 但是不影响。

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

特殊性质 $\text{A}$：保证所有字符串长度不超过 $2$。

特殊性质 $\text{B}$：保证同一个测试用例内，所有字符串互不相同。