311302: CF1968B. Prefiquence

B. Prefiquencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two binary strings $a$ and $b$. A binary string is a string consisting of the characters '0' and '1'.

Your task is to determine the maximum possible number $k$ such that a prefix of string $a$ of length $k$ is a subsequence of string $b$.

A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements.

Input

The first line consists of a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1\le n,m \le 2 \cdot 10^5$) — the length of string $a$ and the length of string $b$, respectively.

The second line of each test case contains a binary string $a$ of length $n$.

The third line of each test case contains a binary string $b$ of length $m$.

It is guaranteed that the sum of values $n$ over all test cases does not exceed $2 \cdot 10^5$. Similarly, the sum of values $m$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single number — the maximum $k$, such that the first $k$ characters of $a$ form a subsequence of $b$.

ExampleInput

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

Output

2
2
1
1
3
0

Note

In the first example, the string '$10$' is a subsequence of '$1\color{red}11\color{red}0$' but the string '$100$' is not. So the answer is $2$.

In the fifth example, $a$='$100$', $b$='$1\color{red}{10}1\color{red}0$', whole string $a$ is a subsequence of string $b$. So the answer is $3$.

In the sixth example, string $b$ does not contain '$1$' so the answer is $0$.

题目大意：
这个题目是关于二进制字符串的问题。给定两个二进制字符串a和b，你的任务是确定最大的数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的一个子序列。题目大意： 这个题目是关于二进制字符串的问题。给定两个二进制字符串a和b，你的任务是确定最大的数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的一个子序列。