AGPC01D - The String Problem

no tags 

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

hide comments
fritzp: 2023-11-08 23:45:30

@hackerito Indeed

hackerito: 2022-07-11 15:20:10

This problem has wrong input(probably extra "\n")

sarthaknegi: 2018-10-20 17:14:10

test case :
1
10 8
aaaaaaaaaa
aaaaaaaa

O/P ?


Added by:imranziad
Date:2017-04-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:AIUB Girls Programming Contest - Spring 2016-17