{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You are given a string $T$ and $n$ (not necessarily distinct) strings $S_1, S_2, \\ldots, S_n$. What is the maximum length of a substring of $T$ that can be formed by choosing some strings from $S_1, S_2, \\ldots, S_n$, and concatenating them in some non decreasing order of length. Please note that there might be multiple non decreasing orders possible.\r\n\r\nFormally,\r\n\r\nConsider all the strings $Y$ that can be obtained as follows:\r\n\r\nInitialize $Y$ as empty string, $L \u003d 0$, $X \u003d \\{1, 2, \\ldots, n\\}$. Choose $0 \\leq t \\leq n$.\r\n\r\nRepeat the following procedure $t$ times:\r\n\r\n- Choose an index $i \\in X$ such that $|S_i| \\geq L$. \r\n- Add $S_i$ to the end of $Y$.\r\n- Replace $L$ by $|S_i|$\r\n- Remove $i$ from $X$.\r\n\r\nWhat is the length of the longest substring of $T$ that can be formed in this way?\r\n\r\n### Input:\r\n\r\n- First line will contain $Q$, number of testcases. Then the testcases follow. \r\n- The first line of each testcase contains the string $T$.\r\n- The second line of each testcase contains $n$.\r\n- $i$-th of the next $n$ lines contain the string $S_i$\r\n\r\n### Output:\r\nFor each testcase, output the length of the longest substring of $T$ that can be formed in the way described. If there is no non empty substring of $T$ that can be formed, print 0.\r\n\r\n### Constraints \r\n- $1 \\leq Q \\leq 10^4$\r\n- $1 \\leq n, |S_i|$\r\n- All strings in the input consist of lowercase english letters only.\r\n- The sum of lengths of all the strings in the input doesn\u0027t exceed $10^5$.\r\n\r\n### Sample Input:\r\n 3\r\n abcdefg\r\n 4\r\n a\r\n b\r\n ef \r\n bcd\r\n abcdefg\r\n 4\r\n a\r\n de\r\n fg\r\n bc\r\n aaa\r\n 2\r\n a\r\n a\r\n\r\n### Sample Output:\r\n 4\r\n 7\r\n 2\r\n\r\n### EXPLANATION:\r\nIn the first testcase, we can choose the strings `a` and `bcd` and concatenate to get the string `abcd`.\r\n\r\nIn the second testcase, you can choose all the strings and concatenate them in the order `a`, `bc`, `de` and `fg` to get `abcdefg`.\r\n\r\nIn the third testcase choose both the strings `a` and `a` to get `aa`. Note that one string can be used only once, and hence we can\u0027t form `aaa`.\r\n"}}]}