You are given two strings $A$ and $B$ of length $N$ and $M$ respectively consisting of lowercase English letters. You can make several strings using characters from $A$. If you use any character of $A$ to make the string, that character will be removed from $A$.

That means if you select an integer $i$ from $1$ to the length of the string $A$ and use $A_i$, then the character $A_i$ will be removed and the string length gets reduced by $1$, the indices of characters to the right of the deleted one also get reduced by $1$.

Find the maximum number of strings you can make the same as that of $B$.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains two space-separated integers $N$ and $M$.
• The second line of each test case contains the string $A$.
• The third line of each test case contains the string $B$.

Output format

For each test case, print the maximum number of strings you can make the same as that of $B$.

Constraints

$1 \leq T \leq 10 \\ 1 \leq N, M \leq 10^5 \\ \text{A and B contains lowercase English letters}$