题目描述

给定 $n$ 个 01 串 $s_1, s_2, \cdots, s_n$ 和另外 $m$ 个 01 串 $t_1, t_2, \cdots, t_m$。对于一个 01 串 $P$，如下定义它的价值：

• 如果存在任何一个 $t_i\,(1 \le i \le m)$ 是 $P$ 的子串，那么 $P$ 的价值为 0

• 否则令 $Set(P) = \{i \mid s_i 是 P 的子串\}$，如果 $Set(P)$ 为空集，那么 $P$ 的价值为 0，否则 $P$ 的价值记为 $Set(P)$ 中最大值减最小值加一，即 $\max\{Set(P)\} - \min\{Set(P)\} + 1$

问对于所有的 01 串，其最大价值可能是多少，输出该最大价值。

输入格式

从文件 string.in 中读入数据。

输入第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n,m$。

接下来 $n$ 行，每行一个 01 串 $s_i$。

接下来 $m$ 行，每行一个 01 串 $t_i$。

输出格式

输出到文件 string.out 中。

对于每组数据：

输出一行一个整数，表示所有 01 串中的最大价值。

样例 1 输入

3
3 2
100
001
010
1001
000
2 1
100
001
00
2 4
100
001
010
1001
000
11

样例 1 输出

3
0
1

样例解释

• 对于第一组数据，存在 01 串 0100 ，记作 $P$，其中 $Set(P) = \{1, 3\}$，价值为 $3 - 1 + 1 = 3$。

• 对于第二组数据，不存在既包含 100 或者 001，又不包含它们公共子串 00 的串，所有串的价值都是 0。

• 对于第三组数据，存在 01 串 100，记作 $P$，其中 $Set(P) = \{1\}$，价值为 $1 - 1 + 1 = 1$。

数据范围及约定

对于 $100\%$ 的数据，满足 $1\le T \le 10^5, 1 \le n \le 10^5, 1 \le m \le 10^5$。对于单个输入文件中的多组数据，保证 $\sum n + \sum m \le 10^5, \sum |s_i| + \sum |t_i| \le 10^6$。

特殊性质 $A$：输入的所有字符串都不包含10这个子串。

样例测试文件

• sample_string1.in/ans 为样例输入输出

• sample_string2.in/ans 满足测试点 $1$ 的约束条件

• sample_string3.in/ans 满足测试点 $2\sim 3$ 的约束条件

• sample_string4.in/ans 满足测试点 $4\sim 5$ 的约束条件

• sample_string5.in/ans 满足测试点 $6\sim 7$ 的约束条件

sample