问题描述

你的任务是确定最大可能的数字k，使得字符串a的长度为k的前缀是字符串b的一个子序列。

如果序列a可以通过删除序列b中的几个（可能是零个或全部）元素得到，那么序列a是序列b的一个子序列。

输入

第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。

每个测试用例的第一行包含两个整数n和m（1≤n,m≤2×10^5）——字符串a的长度和字符串b的长度。

每个测试用例的第二行包含长度为n的二进制字符串a。

每个测试用例的第三行包含长度为m的二进制字符串b。

可以保证所有测试用例中n的总和不超过2×10^5。同样，所有测试用例中m的总和也不超过2×10^5。

输出

对于每个测试用例，输出一个数字——最大k，使得字符串a的前k个字符形成字符串b的一个子序列。

样例

样例输入

6
5 4
10011
1110
3 3
100
110
1 3
1
111
4 4
1011
1111
3 5
100
11010
3 1
100
0

样例输出

2
2
1
1
3
0

### 说明
每个测试的时间限制为2秒  
每个测试的内存限制为256兆字节  
给定两个二进制字符串a和b。二进制字符串是由字符'0'和'1'组成的字符串。