You are given $n$ strings $s_1, s_2, \dots, s_n$ of length at most $\mathbf{8}$.

For each string $s_i$, determine if there exist two strings $s_j$ and $s_k$ such that $s_i = s_j + s_k$. That is, $s_i$ is the concatenation of $s_j$ and $s_k$. Note that $j$ can be equal to $k$.

Recall that the concatenation of strings $s$ and $t$ is $s + t = s_1 s_2 \dots s_p t_1 t_2 \dots t_q$, where $p$ and $q$ are the lengths of strings $s$ and $t$ respectively. For example, concatenation of "code" and "forces" is "codeforces".


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of strings.

Then $n$ lines follow, the $i$-th of which contains non-empty string $s_i$ of length at most $\mathbf{8}$, consisting of lowercase English letters. Among the given $n$ strings, there may be equal (duplicates).

The sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

For each test case, output a binary string of length $n$. The $i$-th bit should be ${1}$ if there exist two strings $s_j$ and $s_k$ where $s_i = s_j + s_k$, and ${0}$ otherwise. Note that $j$ can be equal to $k$.


-----Examples-----

Input
3
5
abab
ab
abc
abacb
c
3
x
xx
xxx
8
codeforc
es
codes
cod
forc
forces
e
code
Output
10100
011
10100101


-----Note-----

In the first test case, we have the following:

$s_1 = s_2 + s_2$, since ${abab} = {ab} + {ab}$. Remember that $j$ can be equal to $k$.

$s_2$ is not the concatenation of any two strings in the list.

$s_3 = s_2 + s_5$, since ${abc} = {ab} + {c}$.

$s_4$ is not the concatenation of any two strings in the list.

$s_5$ is not the concatenation of any two strings in the list.

Since only $s_1$ and $s_3$ satisfy the conditions, only the first and third bits in the answer should be ${1}$, so the answer is ${10100}$.

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Data structures

Complete search


Solutions:
import sys
input = lambda : sys.stdin.readline().strip()
for i in range(int(input())):
	a = int(input())
	b = []
	c = set()
	for i in range(a):
		d = input()
		b.append(d)
		c.add(d)
	count = ''
	for j in b:
		for k in range(1, len(j)):
			if j[k:] in c and j[:k] in c:
				count += '1'
				break
		else:
			count += '0'
	print(count)


import sys
input = lambda : sys.stdin.readline().strip()
n = int(input())
for i in range(n):
	x = int(input())
	nums = [input() for i in range(x)]
	ans = ''
	num = set(nums)
	for i in nums:
		check = True
		for j in range(1, len(i)):
			if i[j:] in num and i[:j] in num:
				ans += '1'
				check = False
				break
		if check:
			ans += '0'
	print(ans)


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def dist(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve() -> None:
	n = int(input())
	words = [input().strip() for _ in range(n)]
	words_set = set(words)
	res = ''
	for word in words:
		for i in range(len(word) - 1):
			if word[:i + 1] in words_set and word[i + 1:] in words_set:
				res += '1'
				break
		else:
			res += '0'
	print(res)

def main() -> None:
	t = int(input())
	for _ in range(t):
		solve()
main()


import sys
import math
from collections import Counter

def gi():
	return list(map(int, sys.stdin.readline().strip().split()))

def gs():
	return sys.stdin.readline().strip()

def fun(a):
	l = len(a)
	d = set(a)
	ans = ''
	for i in a:
		ln = len(i)
		j = 1
		f = 1
		while j < ln:
			x = i[:j]
			if x in d:
				y = i[j:]
				if y in d:
					ans += '1'
					f = 0
					break
			j += 1
		if f:
			ans += '0'
	return ans
for _ in range(int(input())):
	x = int(input())
	ans = []
	for i in range(x):
		ans.append(gs())
	print(fun(ans))


def solve():
	n = int(input())
	s = [input() for i in range(n)]
	d = set(s)
	ans = ''
	for t in s:
		for j in range(1, len(t)):
			if t[:j] in d and t[j:] in d:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)
T = int(input())
for _ in range(T):
	solve()


import sys
T = int(sys.stdin.readline())

def search(s, hash_set):
	for p in range(1, len(s)):
		s1 = s[:p]
		if hash_set.__contains__(s1):
			s2 = s[p:]
			if hash_set.__contains__(s2):
				return '1'
	return '0'
for t in range(T):
	n = int(sys.stdin.readline())
	arr = [sys.stdin.readline().rstrip() for _ in range(n)]
	hash_set = set(arr)
	answer = []
	for (i, s) in enumerate(arr):
		answer.append(search(s, hash_set))
	print(''.join(answer))


def solve(arr, n):
	st = set()
	for i in arr:
		st.add(i)
	ans = ''
	for s in arr:
		answered = False
		for i in range(len(s)):
			if s[:i] in st and s[i:] in st:
				ans += '1'
				answered = True
				break
		if not answered:
			ans += '0'
	return ans

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		strings = []
		for _ in range(n):
			strings.append(input())
		res = solve(strings, n)
		print(res)
main()


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		strings_map = {}
		strings = []
		for _ in range(n):
			string = input()
			if string not in strings_map:
				strings_map[string] = len(string)
			strings.append(string)
		result = ''
		for string in strings:
			added = False
			for i in range(1, len(string)):
				if string[:i] in strings_map and string[i:] in strings_map:
					added = True
					result += '1'
					break
			if not added:
				result += '0'
		print(result)
main()


x = int(input())

def cal(n, arr):
	res = ['0'] * n
	t = set(arr)
	for i in range(n):
		st = arr[i]
		k = len(st)
		if k == 1:
			continue
		for j in range(1, k):
			if st[:j] in t and st[j:] in t:
				res[i] = '1'
				break
	return ''.join(res)
for jj in range(x):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(input())
	print(cal(n, arr))


count = int(input())

def find_true(a, spis):
	for p in range(len(a)):
		if a[:p] in spis and a[p:] in spis:
			return '1'
	return '0'
for i in range(count):
	count_of_strings = int(input())
	string_of_results = ''
	spisok = []
	for j in range(count_of_strings):
		spisok.append(input())
	settium = set(spisok)
	for c in spisok:
		string_of_results += find_true(c, settium)
	print(string_of_results)


import sys
from math import sqrt, ceil, floor, gcd
from collections import Counter, defaultdict
input = lambda : sys.stdin.readline().rstrip('\r\n')

def int_arr():
	return list(map(int, input().split()))

def str_arr():
	return list(map(str, input().split()))

def get_str():
	return map(str, input().split())

def get_int():
	return map(int, input().split())

def get_flo():
	return map(float, input().split())

def lcm(a, b):
	return a * b // gcd(a, b)
mod = 1000000007

def solve():
	n = int(input())
	d = defaultdict(int)
	arr = []
	for i in range(n):
		s = str(input())
		d[s] = 1
		arr.append(s)
	ans = ''
	for string in arr:
		ok = False
		for i in range(1, len(string)):
			(x, y) = (string[:i], string[i:])
			if x in d and y in d:
				ans += '1'
				ok = True
				break
		if not ok:
			ans += '0'
	print(ans)
T = 1
T = int(input())
while T:
	solve()
	T -= 1


for _ in range(int(input())):
	num = int(input())
	array = [input() for k in range(num)]
	newArray = set(array)
	final = []
	for x in array:
		for i in range(1, len(x)):
			if x[:i] in newArray and x[i:] in newArray:
				final.append('1')
				break
		else:
			final.append('0')
	print(''.join(final))


def f(a, s):
	for i in range(1, len(s)):
		if s[:i] in a and s[i:] in a:
			return 1
	return 0
t = input()
for i in range(int(t)):
	n = int(input())
	a = []
	a_set = set()
	for i in range(n):
		k = input()
		a.append(k)
		a_set.add(k)
	ans = ''
	for i in range(n):
		if f(a_set, a[i]):
			ans += '1'
		else:
			ans += '0'
	print(ans)


def sol(arr):
	sett = set(arr)
	ans = []
	for a in arr:
		if any([(a[:i] in sett and a[i:]) in sett for i in range(1, len(a))]):
			ans.append('1')
		else:
			ans.append('0')
	return ans
x = int(input())
for _ in range(x):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(input().strip())
	print(''.join(sol(arr)))


for _ in range(int(input())):
	n = int(input())
	s = [input() for i in range(n)]
	ss = set(s)
	ans = ''
	for st in s:
		for j in range(1, len(st)):
			if st[:j] in ss and st[j:] in ss:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)


for t in range(int(input())):
	n = int(input())
	s = [input() for i in range(n)]
	d = set(s)
	a = ''
	for i in s:
		for j in range(len(i)):
			if i[:j] in d and i[j:] in d:
				a += '1'
				break
		else:
			a += '0'
	print(a)


a = int(input())
ans = []
for i in range(a):
	t = []
	amount = int(input())
	for j in range(amount):
		string = str(input())
		t.append(string)
	s = set(t)
	b = ''
	for word in t:
		for k in range(len(word)):
			if word[k:] in s and word[:k] in s:
				b += '1'
				break
		else:
			b += '0'
	ans.append(b)
for i in ans:
	print(i)


tests = int(input())
for _ in range(tests):
	n = int(input())
	words = []
	for i in range(n):
		words.append(input())
	out = []
	set_words = set(words)
	for word in words:
		for i in range(1, len(word)):
			if word[:i] in set_words and word[i:] in set_words:
				out.append('1')
				break
		else:
			out.append('0')
	print(''.join(out))


import sys
import math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def main():
	for _ in range(int(input())):
		n = int(input())
		ls = []
		st = set()
		for i in range(n):
			x = input()
			ls.append(x)
			st.add(x)
		ans = ''
		for i in range(n):
			ok = False
			temp = ls[i]
			temp_len = len(temp)
			for k in range(1, temp_len):
				if ls[i][:k] in st and ls[i][k:] in st:
					ok = True
			if ok:
				ans += '1'
			else:
				ans += '0'
		print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	l = []
	ans = ''
	for i in range(n):
		l.append(input())
	d = dict(zip(l, l))
	for j in l:
		for k in range(1, len(j)):
			if j[:k] in d and j[k:] in d:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)


def solve_task():
	word_cnt = int(input())
	words = [input() for i in range(word_cnt)]
	words_set = set(words)
	which_words_are_constructable = ''
	for word in words:
		is_constructable = False
		for division_idx in range(1, len(word)):
			substr_left = word[:division_idx]
			substr_right = word[division_idx:]
			if substr_left in words_set and substr_right in words_set:
				is_constructable = True
				break
		which_words_are_constructable += '1' if is_constructable else '0'
	return which_words_are_constructable
testcases_cnt = int(input())
while testcases_cnt:
	print(solve_task())
	testcases_cnt -= 1


I = input
for _ in [0] * int(I()):
	n = int(I())
	a = [I() for _ in range(n)]
	d = set(a)
	z = ['0'] * n
	for (i, s) in enumerate(a):
		for j in range(1, len(s)):
			if s[:j] in d and s[j:] in d:
				z[i] = '1'
	print(''.join(z))


def bleh(s):
	for j in range(1, len(s)):
		if s[:j] in mySet and s[j:] in mySet:
			return '1'
	return '0'
for _ in range(int(input())):
	arr = []
	mySet = set()
	n = int(input())
	for _ in range(n):
		arr.append(input())
		mySet.add(arr[-1])
	ans = ''
	for s in arr:
		ans += bleh(s)
	print(ans)


from pickle import FALSE

def test_case(strings):
	hash_map = {}
	for s in strings:
		if s not in hash_map:
			hash_map[s] = 1
	res = ''
	for s in strings:
		check = -1
		for index in range(1, len(s)):
			if s[:index] in hash_map and s[index:] in hash_map:
				check = 1
			elif check != 1:
				check = 0
		if check == 1:
			res += '1'
		else:
			res += '0'
	return res
num_case = int(input())
for case in range(num_case):
	n = int(input())
	strings = []
	for _ in range(n):
		strings.append(str(input()))
	print(test_case(strings), end='\n')


out = []
for _ in range(int(input())):
	n = int(input())
	st = set()
	stl = []
	for i in range(n):
		s = input()
		stl.append(s)
		st.add(s)
	ans = []
	for s in stl:
		for i in range(1, len(s)):
			if s[:i] in st and s[i:] in st:
				ans.append('1')
				break
		else:
			ans.append('0')
	out.append(''.join(ans))
for i in out:
	print(i)


for _ in range(int(input())):
	n = int(input())
	s = [input() for _ in range(n)]
	u = set(s)
	ans = []
	for x in s:
		for i in range(1, len(x)):
			if x[:i] in u and x[i:] in u:
				ans.append('1')
				break
		else:
			ans.append('0')
	print(''.join(ans))


for i in range(int(input())):
	n = int(input())
	l = []
	for j in range(n):
		l.append(input())
	z = set(l)
	o = ''
	for k in l:
		a = len(k)
		for b in range(1, a):
			if k[0:b] in z and k[b:] in z:
				o += '1'
				break
		else:
			o += '0'
	print(o)


for _ in range(int(input())):
	n = int(input())
	a = [input() for a in range(n)]
	s = set(a)
	ans = ''
	for si in a:
		for i in range(len(si)):
			if si[:i] in s and si[i:] in s:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)


for i in range(int(input())):
	num = int(input())
	lis = [input() for _ in range(num)]
	new = set(lis)
	ans = ''
	for j in lis:
		for k in range(1, len(j)):
			if j[:k] in new and j[k:] in new:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [input() for i in range(n)]
	b = set(l)
	ans = ''
	for j in l:
		p = False
		for i in range(1, len(j)):
			if j[:i] in b and j[i:] in b:
				p = True
				break
		ans += '1' if p else '0'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	strings = []
	for j in range(n):
		strings.append(input())
	st = set(strings)
	ans = ''
	for i in strings:
		for j in range(1, len(i)):
			if i[:j] in st and i[j:] in st:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = []
	s = set()
	res = ''
	for i in range(n):
		a = input()
		l.append(a)
		s.add(a)
	for i in l:
		for j in range(1, len(i)):
			if i[j:] in s and i[:j] in s:
				res += '1'
				break
		else:
			res += '0'
	print(res)


for _ in range(int(input())):
	n = int(input())
	l = []
	ans = ['0'] * n
	for i in range(n):
		l.append(input())
	s = set(l)
	for (k, word) in enumerate(l):
		for i in range(1, 8):
			if word[:i] in s and word[i:] in s:
				ans[k] = '1'
	print(''.join(ans))


for _ in range(int(input())):
	leng = int(input())
	lis = []
	for i in range(leng):
		lis.append(input())
	se = set(lis)
	ans = ''
	for i in lis:
		true = True
		for x in range(len(i)):
			if i[x:] in se and i[:x] in se:
				ans += '1'
				true = False
				break
		if true:
			ans += '0'
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = []
	t = []
	for j in range(n):
		s.append(input())
	q = set(s)
	for k in s:
		for m in range(1, len(k)):
			if k[:m] in q and k[m:] in q:
				t.append('1')
				break
		else:
			t.append('0')
	print(''.join(t))


for _ in range(int(input())):
	n = int(input())
	a = ''
	s = [input() for i in range(n)]
	d = set(s)
	for (i, ss) in enumerate(s):
		tr = False
		for j in range(1, len(ss)):
			if ss[:j] in d and ss[j:] in d:
				tr = True
				break
		if tr == True:
			a += '1'
		else:
			a += '0'
	print(a)


for _ in range(int(input())):
	n = int(input())
	l = []
	s = ''
	for i in range(n):
		l.append(input())
	st = set(l)
	for i in l:
		for j in range(1, len(i)):
			if i[:j] in st and i[j:] in st:
				s += '1'
				break
		else:
			s += '0'
	print(s)


import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
	n = int(sys.stdin.readline().strip())
	wd = set()
	ws = []
	r = ''
	for _ in range(n):
		w = sys.stdin.readline().strip()
		wd.add(w)
		ws.append(w)
	for w in ws:
		if len(w) == 1:
			r += '0'
			continue
		f = 0
		for i in range(len(w)):
			if w[:i] in wd and w[i:] in wd:
				f += 1
				break
		r += str(f)
	print(r)


n = int(input())
for _ in range(n):
	n1 = int(input())
	x = []
	for _ in range(n1):
		x.append(input())
	y = set(x)
	answer = ''
	for i in x:
		for j in range(1, len(i)):
			if i[:j] in y and i[j:] in y:
				answer += '1'
				break
		else:
			answer += '0'
	print(answer)


n_test_cases = int(input())
for _ in range(n_test_cases):
	n_str = int(input())
	str_list = []
	for i in range(n_str):
		str_list.append(input())
	str_set = set(str_list)
	result = ''
	for item in str_list:
		is_exist = False
		for i in range(1, len(item)):
			if item[:i] in str_set and item[i:] in str_set:
				is_exist = True
		if is_exist:
			result += '1'
		else:
			result += '0'
	print(result)


for _ in range(int(input())):
	n = int(input())
	arr = [input() for _ in range(n)]
	ss = set(arr)
	ans = ''
	for s in arr:
		ok = False
		for i in range(len(s)):
			if s[:i] in ss and s[i:] in ss:
				ok = True
				break
		if ok:
			ans += '1'
		else:
			ans += '0'
	print(ans)


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = []
	ok = set()
	for i in range(n):
		s = input()
		A.append(s)
		ok.add(s)
	ans = ''
	for s in A:
		flag = 0
		for i in range(8):
			one = s[:i]
			two = s[i:]
			if one in ok and two in ok:
				flag = 1
				break
		if flag:
			ans += '1'
		else:
			ans += '0'
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	b = [input() for j in range(n)]
	s = set(b)
	ans = ''
	for elem in b:
		for j in range(1, len(elem)):
			if elem[:j] in s and elem[j:] in s:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	d = {}
	res = [0] * n
	for i in range(n):
		s = input()
		if s not in d:
			d[s] = [i]
		else:
			d[s].append(i)
	for s in d:
		for i in range(1, len(s)):
			if s[:i] in d and s[i:] in d:
				for i in d[s]:
					res[i] = 1
				break
	print(''.join([str(x) for x in res]))


for h in range(int(input())):
	n = int(input())
	d = {}
	x = []
	for i in range(n):
		s = input()
		x.append(s)
		d[s] = 1
	z = []
	for i in x:
		f = '0'
		for j in range(1, len(i)):
			if i[:j] in d and i[j:] in d:
				f = '1'
				break
		z.append(f)
	print(''.join(z))


from collections import *
import sys
for _ in range(int(input())):
	n = int(input())
	strings = []
	for _ in range(n):
		strings.append(input())
	sett = set(strings)
	ans = ''
	for i in strings:
		for ii in range(1, len(i)):
			if i[:ii] in sett and i[ii:] in sett:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)


from heapq import heappop, heappush
import math
from sys import stdin, stdout
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right, insort_right
inf = int(1e+19)
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	ans = ''
	st = set()
	l = []
	for i in range(n):
		s = input().strip()
		st.add(s)
		l.append(s)
	for i in l:
		key = 0
		for j in range(len(i)):
			if i[:j] in st and i[j:] in st:
				key = 1
				break
		ans += str(key)
	print(ans)


nn = int(input())
for _ in range(nn):
	m = int(input())
	aa = []
	bb = set()
	for i in range(m):
		ss = input()
		bb.add(ss)
		aa.append(ss)
	s = ''
	for x in aa:
		dd = len(x)
		for i in range(1, dd):
			if x[:i] in bb and x[i:] in bb:
				s += '1'
				break
		else:
			s += '0'
	print(s)


for i in range(int(input())):
	n = int(input())
	ss = [input() for j in range(n)]
	s_ = set()
	res = ''
	for s in ss:
		s_.add(s)
	for i in ss:
		flag = False
		for j in range(1, len(i)):
			if i[:j] in s_ and i[j:] in s_:
				flag = True
				break
		if flag:
			res += '1'
		else:
			res += '0'
	print(res)


from operator import length_hint
for _ in range(int(input())):
	n = int(input())
	s = [input() for aaa in range(n)]
	result = ''
	set_s = set(s)
	for x in s:
		flag = '0'
		for i in range(1, len(x)):
			if x[:i] in set_s and x[i:] in set_s:
				flag = '1'
				break
		result += flag
	print(result)


def res():
	for x in range(int(input())):
		n = int(input())
		l = []
		m = dict()
		for i in range(n):
			a = input()
			l.append(a)
			m[a] = 1
		res = ''
		for i in l:
			c = 0
			for j in range(1, len(i)):
				s = i[:j]
				ss = i[j:]
				if s in m and ss in m:
					c = 1
					break
			if c:
				res += '1'
			else:
				res += '0'
		print(res)
res()


def solve():
	n = int(input())
	arr = [input() for i in range(n)]
	s = set(arr)
	for w in arr:
		ans = False
		for i in range(1, len(w)):
			if w[:i] in s and w[i:] in s:
				ans = True
		if ans:
			print(1, end='')
		else:
			print(0, end='')
	print()
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = [input() for i in range(n)]
	b = set(a)
	req = ''
	for i in a:
		for j in range(1, len(i)):
			if i[:j] in b and i[j:] in b:
				req += '1'
				break
		else:
			req += '0'
	print(req)


t = int(input())
for _ in range(t):
	n = int(input())
	s = set()
	l = []
	for _ in range(n):
		l.append(input())
	s = set(l)
	ans = ''
	for i in range(n):
		c = l[i]
		if len(c) < 2:
			ans += '0'
			continue
		f = False
		for j in range(1, len(c)):
			if c[:j] in s and c[j:] in s:
				f = True
				ans += '1'
				break
		if not f:
			ans += '0'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	e = [input() for i in range(n)]
	s = set(e)
	otv = ''
	for i in e:
		r = i
		flag = False
		for j in range(1, len(r)):
			if r[:j] in s and r[j:] in s:
				flag = True
				break
		otv += f'{int(flag)}'
	print(otv)


for w in range(int(input())):
	n = int(input())
	v = [input() for i in range(n)]
	ans = ''
	dct = {}
	for i in v:
		dct[i] = True
	for x in v:
		b = False
		for i in range(len(x)):
			if x[:i] in dct and x[i:] in dct:
				b = True
		ans += ('0', '1')[b]
	print(ans)


import functools

def solve():
	sz = int(input())
	s = []
	mp = {}
	for i in range(sz):
		x = input()
		s.append(x)
		mp[x] = True
	ans = ['0' for x in range(sz)]
	for (idx, k) in zip(range(sz), s):
		for i in range(len(k)):
			x = k[:i]
			y = k[i:]
			if x in mp and y in mp:
				ans[idx] = '1'
	return ans
n = int(input())
for i in range(n):
	print(''.join(solve()))


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	b = set()
	for i in range(n):
		s = input()
		a.append(s)
		b.add(s)
	ans = ''
	for i in a:
		for j in range(len(i)):
			if i[:j] in b and i[j:] in b:
				ans += '1'
				break
		else:
			ans += '0'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = []
	dic = {}
	for i in range(n):
		s = input()
		l.append(s)
		dic[s] = True
	ok = ''
	for s in l:
		a = '0'
		for j in range(1, len(s)):
			if s[:j] in dic and s[j:] in dic and (dic[s[:j]] == True) and (dic[s[j:]] == True):
				a = '1'
				break
		ok += a
	print(ok)


t = int(input())
for x in range(t):
	n = int(input())
	l = [input() for i in range(n)]
	s = set(l)
	ans = ''
	for k in l:
		for i in range(len(k)):
			if k[:i] in s and k[i:] in s:
				if k[:i] in s and k[i:] in s:
					ans += '1'
					break
		else:
			ans += '0'
	print(ans)


def print_hi():
	s = ''
	check = False
	r = input()
	t = int(r)
	while t > 0:
		dic = []
		b = input()
		n = int(b)
		while n > 0:
			n -= 1
			g = input()
			dic.append(g)
		s = ''
		st = set(dic)
		for i in dic:
			check = False
			for f in range(0, len(i) - 1):
				if i[0:f + 1] in st and i[f + 1:len(i)] in st:
					s += '1'
					check = True
					break
			if not check:
				s += '0'
		t -= 1
		print(s)
print_hi()


tests = int(input())
for i in range(tests):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(input())
	sett = set(arr)
	res = ''
	for s in arr:
		added = False
		for i in range(1, 9):
			if s[:i] in sett:
				if s[i:] in sett:
					res += '1'
					added = True
					break
		if not added:
			res += '0'
	print(res)


for _ in range(int(input())):
	n = int(input())
	c = ''
	a = []
	for i in range(n):
		a += [input()]
	d = {}
	for i in a:
		d[i] = 0
	for i in a:
		for j in range(1, 8):
			if i[:j] in d and i[j:] in d:
				c += '1'
				break
		else:
			c += '0'
	print(c)


for _ in range(int(input())):
	n = int(input())
	ans = []
	for i in range(n):
		ans.append(input())
	strings = set(ans)
	arr = [0] * n
	for i in range(n):
		s = ans[i]
		for j in range(len(s)):
			if s[:j] in strings and s[j:] in strings:
				arr[i] = 1
				break
	print(''.join(map(str, arr)))


t = int(input())
for _ in range(t):
	n = int(input())
	answers = ['0'] * n
	a = []
	for i in range(n):
		s = input()
		a.append(s)
	st = set(a)
	for (j, string) in enumerate(a):
		for i in range(len(string)):
			if string[:i] in st and string[i:] in st:
				answers[j] = '1'
				break
	print(''.join(answers))


def resolve(N, list_1):
	result = ''
	set_1 = set()
	for index in range(N):
		set_1.add(list_1[index])
	for index in range(N):
		str_1 = list_1[index]
		length = len(str_1)
		flag = False
		for index_2 in range(1, length):
			before_str = str_1[:index_2]
			after_str = str_1[index_2:]
			if before_str in set_1 and after_str in set_1:
				result += '1'
				flag = True
				break
		if not flag:
			result += '0'
	return result

def read_input():
	N = int(input())
	list_1 = []
	for index in range(N):
		temp_2 = input()
		list_1.append(temp_2)
	return (N, list_1)
case_num = int(input())
if not case_num == 0:
	for index in range(case_num):
		(N, list_1) = read_input()
		res = resolve(N, list_1)
		print(res)


t = int(input())

def solve(n, s):
	d = dict()
	for i in range(n):
		if s[i] in d:
			d[s[i]] += 1
		else:
			d[s[i]] = 1
	ans = ''
	for i in range(n):
		ok = False
		for j in range(len(s[i])):
			if s[i][:j] in d and s[i][j:] in d:
				ok = True
		if ok:
			ans += '1'
		else:
			ans += '0'
	return ans
for i in range(t):
	n = int(input())
	s = [input() for i in range(n)]
	ans = ''
	print(solve(n, s))


t = int(input())
for _ in range(t):
	n = int(input())
	strs = [input() for _ in range(n)]
	s = set(strs)
	ans = ''
	for string in strs:
		found = False
		for i in range(len(string)):
			if string[:i] in s and string[i:] in s:
				found = True
				break
		ans += '1' if found else '0'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [input() for i in range(n)]
	s = set(a)
	z = ''
	for i in range(n):
		for j in range(1, len(a[i])):
			if a[i][:j] in s and a[i][j:] in s:
				z += '1'
				break
		else:
			z += '0'
	print(z)


for t in range(int(input())):
	n = int(input())
	s = []
	k = []
	for i in range(n):
		s.append(input())
	s2 = set(s)
	for i in s:
		cnt = '0'
		for j in range(1, len(i)):
			if i[:j] in s2 and i[j:] in s2:
				cnt = '1'
				break
		k.append(cnt)
	print(''.join(k))


import sys
import math
from itertools import combinations
inut = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	dat = []
	for i in range(n):
		dat.append(input())
	ans = {}
	for i in dat:
		ans[i] = 0
	o = ''
	for i in dat:
		f = 0
		for j in range(1, len(i)):
			if i[:j] in ans and i[j:] in ans:
				o += '1'
				f = 1
				break
		if not f:
			o += '0'
	print(o)


from collections import *

def solve():
	n = int(input())
	s = []
	for i in range(n):
		s.append(input().strip())
	sets = set(s)
	ans = []
	for i in s:
		leni = len(i)
		if leni > 1:
			flag = True
			for j in range(1, leni):
				if i[:j] in sets and i[j:] in sets:
					ans.append('1')
					flag = False
					break
			if flag:
				ans.append('0')
		else:
			ans.append('0')
	return ''.join(ans)
for _ in range(int(input())):
	ans = solve()
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = []
	dic = {}
	for j in range(n):
		arr.append(input())
		dic[arr[-1]] = None
	for k in dic:
		for m in range(len(k) - 1):
			if k[0:m + 1] in dic and k[m + 1:] in dic:
				dic[k] = '1'
				break
		else:
			dic[k] = '0'
	ans = ''
	for p in range(n):
		ans += dic[arr[p]]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	si = [input() for _ in range(n)]
	Si = set(si)
	ans = ''
	for i in si:
		for l in range(len(i) - 1):
			if i[:l + 1] in Si and i[l + 1:] in Si:
				ans = ans + '1'
				break
		else:
			ans = ans + '0'
	print(ans)


test_case_number = int(input())
for _ in range(test_case_number):
	string_number = int(input())
	strings = []
	dic_strings = {}
	for i in range(string_number):
		strings.append(input())
		dic_strings[strings[i]] = True
	results = ''
	flag = False
	for string in strings:
		flag = False
		for i in range(1, len(string)):
			if string[:i] in dic_strings and string[i:] in dic_strings:
				results = results + '1'
				flag = True
				break
		if not flag:
			results = results + '0'
	print(results)


for _ in range(int(input())):
	n = int(input())
	l = []
	s = set()
	for i in range(n):
		temp = input()
		l.append(temp[:])
		s.add(temp[:])
	ans = ''
	for i in l:
		f = False
		for j in range(1, len(i)):
			if i[:j] in s and i[j:] in s:
				f = True
		if f:
			ans += '1'
		else:
			ans += '0'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lst = []
	st = set({})
	for i in range(n):
		lst.append(input())
		st.add(lst[i])
	ans = ''
	for item in lst:
		flag = False
		for i in range(len(item)):
			if item[:i] in st and item[i:] in st:
				flag = True
				break
		ans += '1' if flag else '0'
	print(ans)


def solve():
	n = int(input())
	(s, t, w) = ([], '', {})
	for i in range(n):
		a = input()
		s.append(a)
		w[a] = True
	for i in range(n):
		ok = False
		for j in range(1, len(s[i])):
			pref = s[i][:j]
			suff = s[i][j:]
			if pref in w and suff in w:
				ok = True
				break
		t += str(int(ok))
	return t
t = int(input())
ans = []
while t:
	ans.append(str(solve()))
	t -= 1
print('\n'.join(ans))


for _ in range(int(input())):
	n = int(input())
	mp = set()
	nums = []
	for i in range(n):
		s = input()
		mp.add(s)
		nums.append(s)
	ans = []
	for i in nums:
		f = '0'
		for j in range(len(i)):
			if i[:j] in mp and i[j:] in mp:
				f = '1'
				break
		ans.append(f)
	print(''.join(ans))