A. Вам заданы две бинарные строки...
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам заданы две бинарные строки $$$x$$$ и $$$y$$$, которые являются двоичными представлениями некоторых чисел (назовем их $$$f(x)$$$ и $$$f(y)$$$). Вы можете выбрать целое число $$$k \ge 0$$$, посчитать значение $$$s_k = f(x) + f(y) \cdot 2^k$$$ и выписать двоичное представление $$$s_k$$$ в обратном порядке (назовем его $$$rev_k$$$). Например, пусть $$$x = 1010$$$ и $$$y = 11$$$; вы выбрали $$$k = 1$$$, и так как $$$2^1 = 10_2$$$, то $$$s_k = 1010_2 + 11_2 \cdot 10_2 = 10000_2$$$ и $$$rev_k = 00001$$$.

Для заданных $$$x$$$ и $$$y$$$, вам необходимо выбрать такое целое $$$k$$$, что $$$rev_k$$$ — лексикографически минимально (прочтите примечание, если не знаете, что означает «лексикографически»).

Гарантируется, что при заданных ограничениях $$$k$$$ существует и конечно.

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

В первой строке задано одно число $$$T$$$ ($$$1 \le T \le 100$$$) — количество запросов.

Следующие $$$2T$$$ строк содержат описание запросов: две строки на запрос. В первой строке задана бинарная строка $$$x$$$, состоящая не более чем из $$$10^5$$$ символов, каждый из которых либо 0, либо 1.

Во второй строке задана бинарная строка $$$y$$$, также состоящая не более чем из $$$10^5$$$ символов, каждый из которых либо 0, либо 1.

Гарантируется, что $$$1 \le f(y) \le f(x)$$$ (где $$$f(x)$$$ — число, представленное как $$$x$$$, и $$$f(y)$$$ — число, представленное как $$$y$$$), обе записи не содержат лидирующих нулей, суммарная длина $$$x$$$ по всех запросам не превосходит $$$10^5$$$, суммарная длина $$$y$$$ по всем запросам также не превосходит $$$10^5$$$.

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

Выведите $$$T$$$ целых чисел (по одному на запрос). Для каждого запроса выведите такое $$$k$$$, что $$$rev_k$$$ — лексикографически минимальное.

Пример
Входные данные
4
1010
11
10001
110
1
1
1010101010101
11110000
Выходные данные
1
3
0
0
Примечание

Первый запрос разобран в условии.

Во втором запросе выгодно выбрать $$$k = 3$$$. $$$2^3 = 1000_2$$$, а потому $$$s_3 = 10001_2 + 110_2 \cdot 1000_2 = 10001 + 110000 = 1000001$$$ и $$$rev_3 = 1000001$$$. Если, например, $$$k = 0$$$, то $$$s_0 = 10111$$$ и $$$rev_0 = 11101$$$, а $$$rev_3 = 1000001$$$ лексикографически меньше, чем $$$rev_0 = 11101$$$.

В третьем запросе $$$s_0 = 10$$$ и $$$rev_0 = 01$$$. Например, $$$s_2 = 101$$$ и $$$rev_2 = 101$$$. И $$$01$$$ лексикографически меньше, чем $$$101$$$.

Цитата с английской Вики (вольный перевод): «Для того, чтобы определить, какая из двух строк идет первой в лексикографическом порядке, сначала сравнивают их первые буквы. Если они различаются, то первой идет строка, чья первая буква встречается в алфавите раньше. Если первые буквы совпадают, то сравниваются вторые буквы, и так далее. Если была достигнута ситуация, когда в одной строке больше нет букв, а в другой есть, то первая (более короткая) считается меньше.»