给你 $$$n$$$ 个字符串 $$$s_1, s_2, \dots, s_n$$$,长度最多为 $$$\mathbf{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$$$ 行,其中第 $$$i$$$ 包含非空字符串 $$$s_i$$$,长度最多为 $$$\mathbf{8}$$$,由小写英文字母组成。在给定的 $$$n$$$ 字符串中,可能存在相等(重复)。
所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出长度为 $$$n$$$ 的二进制字符串。如果存在两个字符串 $$$s_j$$$ 和 $$$s_k$$$,其中 $$$s_i = s_j + s_k$$$,则第 $$$i$$$ 位应为 $$$\texttt{1}$$$,否则为 $$$\texttt{0}$$$。请注意,$$$j$$$ 可以等于 $$$k$$$。
示例
输入 #1
3 5 abab ab abc abacb c 3 x xx xxx 8 codeforc es codes cod forc forces e code
输出 #1
10100 011 10100101
注意
在第一个测试用例中,我们有以下内容:
- $$$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$$$ 不是列表中任何两个字符串的串联。