Description

String $A$ has $N$ substrings $B_1,B_2,...,B_n$. If we place each of these $n$ substrings at exactly one position where it occurs in $A$ (substrings may overlap), then some characters in $A$ will be covered by these $N$ substrings. Find the minimum and maximum possible numbers of covered characters in $A$.

Input Format

The first line contains a positive integer $T$, the number of test cases. It is guaranteed that $T \le 10$.

Then the $T$ test cases follow. For each test case:

• The first line contains a string of lowercase letters, the main string $A$.
• The second line contains an integer $N$, the number of substrings.
• The next $N$ lines each contain a string of lowercase letters, describing a substring. It is guaranteed that every substring occurs in the main string.

Output Format

Output $T$ lines, one for each test case. Each line contains two integers $Minans$ and $Maxans$, the minimum and maximum numbers of characters that can be covered, respectively.

2
hello
4
he
l
l
o
abacaba
4
ab
ba
a
c

4 5 
4 6

Hint

Constraints: $|A| \le 10000$, $N \le 4$, substring length $\le 10000$.

Translated by ChatGPT 5