Вам заданы две бинарные строки \(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\) целых чисел (по одному на запрос). Для каждого запроса выведите такое \(k\), что \(rev_k\) — лексикографически минимальное.
Примечание
Первый запрос разобран в условии.
Во втором запросе выгодно выбрать \(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\).
Цитата с английской Вики (вольный перевод): «Для того, чтобы определить, какая из двух строк идет первой в лексикографическом порядке, сначала сравнивают их первые буквы. Если они различаются, то первой идет строка, чья первая буква встречается в алфавите раньше. Если первые буквы совпадают, то сравниваются вторые буквы, и так далее. Если была достигнута ситуация, когда в одной строке больше нет букв, а в другой есть, то первая (более короткая) считается меньше.»
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1010
11
10001
110
1
1
1010101010101
11110000
|
1
3
0
0
|