Mina and Tina love to play with strings. Mina's favorite string name is A and Tina's favorite string name is B. One day Tina stole Mina's string. Now she is wondering the maximum number of string B she can make using characters from string A. After trying for a long period of time she failed to figure out the number. Now she is asking for your help to find the number.

Input

Input starts with T (1 <= T <= 100), denoting the number of test case.

Each of the test case contains 3 line. First line contains n and m (1 <= n, m <= 100000). n and m are the size of string A and B respectively. Second line contains string A and third line contains B.

Input contains only lower case English letter.

Output

For each testcase, find the maximum number of string B can be created using characters from string A.

Example

Input:
2
4 2
abcd
ca
4 1
abcd
e

Output:
1
0