P14113 [IAMOI R4] Completely Furious


General Gold has two strings $s$ and $t$, each of length $n$. He defines the **fury value** of a string as the number of occurrences of the substring `CDNL`. Now, he wants to select a substring $s'$ from $s$ with length at most $m$, and a substring $t'$ from $t$ with length at most $k$, such that the concatenated string $s' + t'$ (in this order) maximizes the fury value. You need to help him find this value. A substring is a contiguous sequence of characters from the original string.

**There are multiple test cases.** The first line contains an integer $T$, indicating the number of test cases. For each test case: - The first line contains three positive integers $n$, $m$, $k$. - The second line contains a string $s$ of length $n$. - The third line contains a string $t$ of length $n$.

For each test case, output one line containing a single integer—the answer.

**【Sample Explanation】** For the first test case, the optimal concatenated string is `CDNLCDNL`, which contains $2$ occurrences of `CDNL`, so the fury value is $2$. For the second test case, the optimal concatenated string is `CDNL`, which contains $1$ occurrence of `CDNL`, so the fury value is $1$. **【Constraints】** | Test Point | $n \leq$ | $m, k$ | Points | |:-:|:-:|:-:|:-:| | $1$ | $10^5$ | $=n$ | $20$ | | $2$ | $10$ | $\leq n$ | $30$ | | $3$ | $100$ | ^ | $20$ | | $4$ | $10^5$ | $\leq 10$ | ^ | | $5$ | ^ | $\leq n$ | $10$ | For all test cases, it is guaranteed that: $1 \le T \le 10$, $1 \le n, m, k \le 10^5$, and $s$, $t$ consist only of uppercase letters `C`, `D`, `N`, `L`.