题目描述

给您 $n$ 个字符串 $s_1,s_2,…,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_1s_2…s_pt_1t_2…t_q$，其中 $p$ 和 $q$ 分别是字符串 $s$ 和 $t$ 的长度。例如，guangtou 和 qiang 的连接就是 guangtouqiang。

输入格式

第一行包含单个整数 $t(1≤t≤10^4)$ 代表测试用例数。

每个测试用例的第一行包含单个整数 $n(1≤n≤10^5)$ 代表字符串数。

随后是 $n$ 行，其中第 $i$ 行包含长度最多为 $8$ 的非空字符串 $s_i$，由小写英文字母组成。在给定的 $n$ 个字符串中，可能有相等的（重复的）。

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

输出格式

对于每个测试用例，输出长度为 $n$ 的二进制字符串。如果存在两个字符串 $s_j$ 和 $s_k$ 满足 $s_i=s_j+s_k$，则第 $i$ 位应为 $1$，否则为 $0$。注意 $j$ 可以等于 $k$。

测试样例

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

10100
011
10100101

样例说明

在第一个测试用例中，我们有以下内容：

• $s_1=s_2+s_2$，因为 abab=ab+ab。记住 $j$ 可以等于 $k$。
• $s_2$ 不是列表中任何两个字符串的串联。
• $s_3=s_2+s_5$，因为 abc=ab+c。
• $s_4$ 不是列表中任何两个字符串的串联。
• $s_5$ 不是列表中任何两个字符串的串联。

因为只有 $s_1$ 和 $s_3$ 满足条件，所以答案中只有第一和第三位应该是 $1$，所以答案是 10100。