Longest Valid Substring

You are given a string S and a set of forbidden substrings. Your task is to find the length of the longest contiguous substring of S that does not contain any of the forbidden substrings. A substring is considered valid if none of the forbidden substrings appear anywhere within it. Formally, if the length of a valid substring is ( \ell ), then for every forbidden substring ( f ), the substring does not satisfy ( f \subseteq s ) where ( s ) is any contiguous segment of S. This problem is to be solved for multiple test cases.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer ( T ) (the number of test cases). For each test case, the input format is as follows:

1. A line containing the string ( S ).
2. A line containing an integer ( N ) representing the number of forbidden substrings.
3. ( N ) lines each containing a forbidden substring.

Constraints can be assumed to be such that a simple brute-force solution is acceptable.

outputFormat

For each test case, output on a separate line a single integer representing the length of the longest substring of ( S ) that does not contain any forbidden substring. The output is written to standard output (stdout).## sample

5
abracadabra
2
abra
cad
xyzzy
1
yz
a
1
a
abcde
0
aaaaa
1
aa

3
3
0
5
1