← Home
write a go solution for Description:
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 Format:
The first line consists of a single integer t (1<=t<=10^4) — the number of test cases.

The first line of each test case contains two integers n and m (1<=n,m<=2*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*10^5. Similarly, the sum of values m over all test cases does not exceed 2*10^5.

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

Note:
In the first example, the string '10' is a subsequence of '1colorred11colorred0' but the string '100' is not. So the answer is 2.

In the fifth example, a='100', b='1colorred101colorred0', 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.. Output only the code with no comments, explanation, or additional text.