Description

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.

Input Format

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$.

Output Format

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

2
4 4 4
CDNL
CDNL
2 2 2
CD
NL

2
1

Hint

【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】

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.