A string $A$ has $N$ substrings $B_1, B_2, \dots, B_N$. If these $N$ substrings are each placed at exactly one of their occurrences in $A$ (substrings may overlap), then some characters in $A$ will be covered by these $N$ substrings. Find the minimum and maximum number of characters in $A$ that can be covered.
Input
The first line contains a positive integer $T$, representing the number of test cases. It is guaranteed that $T \le 10$. Each test case is described as follows: The first line contains a string consisting of lowercase letters, representing the main string $A$. The second line contains an integer $N$, representing the number of substrings. The next $N$ lines each contain a string consisting of lowercase letters, describing a substring. It is guaranteed that all substrings appear in the main string.
Output
Output $T$ lines, each containing the answer for the corresponding test case. Each line should contain two integers $minAns$ and $maxAns$, representing the minimum and maximum number of characters in $A$ that can be covered, respectively.
Subtasks
In the table below, the symbol $|S|$ denotes the total number of characters in string $S$.
| Test Case ID | $ | A | $ | $N$ | $ | B_i | $ |
|---|---|---|---|---|---|---|---|
| 1 | $\le 10$ | $\le 2$ | $\le 4$ | ||||
| 2 | $\le 1000$ | $\le 2$ | $\le 50$ | ||||
| 3~5 | $\le 1000$ | $\le 4$ | $\le 50$ | ||||
| 6~8 | $\le 5000$ | $\le 4$ | $\le 500$ | ||||
| 9,10 | $\le 10000$ | $\le 4$ | $\le 1000$ |
Examples
Input 1
2 hello 4 he l l o abacaba 4 ab ba a c
Output 1
4 5 4 6