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