B. Префиксная подпоследовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны две двоичные строки $$$a$$$ и $$$b$$$. Двоичная строка — это строка, состоящая из символов '0' и '1'.

Ваша задача — определить максимально возможное число $$$k$$$, такое что префикс строки $$$a$$$ длины $$$k$$$ является подпоследовательностью строки $$$b$$$.

Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов.

Входные данные

Первая строка состоит из одного целого числа $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два числа $$$n$$$ и $$$m$$$ ($$$1\le n,m \le 2 \cdot 10^5$$$) — длина строки $$$a$$$ и длина строки $$$b$$$ соответственно.

Вторая строка каждого набора содержит двоичную строку $$$a$$$ длиной $$$n$$$.

Третья строка каждого набора содержит двоичную строку $$$b$$$ длиной $$$m$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$. Аналогично, сумма значений $$$m$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — максимальное $$$k$$$, такое что первые $$$k$$$ символов $$$a$$$ являются подпоследовательностью $$$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
Примечание

В первом примере строка '$$$10$$$' является подпоследовательностью '$$$1\color{red}11\color{red}0$$$', но строка '$$$100$$$' — нет. Таким образом, ответ равен $$$2$$$.

В пятом примере $$$a$$$='$$$100$$$', $$$b$$$='$$$1\color{red}{10}1\color{red}0$$$', вся строка $$$a$$$ является подпоследовательностью строки $$$b$$$. Таким образом, ответ равен $$$3$$$.

В шестом примере строка $$$b$$$ не содержит '$$$1$$$', поэтому ответ равен $$$0$$$.