CF1202A.You Are Given Two Binary Strings...

You are given two binary strings $x$ and $y$, which are binary representations of some two integers (let's denote these integers as $f(x)$ and $f(y)$). You can choose any integer $k \ge 0$, calculate the expression $s_k = f(x) + f(y) \cdot 2^k$ and write the binary representation of $s_k$ in reverse order (let's denote it as $rev_k$). For example, let $x = 1010$ and $y = 11$; you've chosen $k = 1$ and, since $2^1 = 10_2$, so $s_k = 1010_2 + 11_2 \cdot 10_2 = 10000_2$ and $rev_k = 00001$.

For given $x$ and $y$, you need to choose such $k$ that $rev_k$ is lexicographically minimal (read notes if you don't know what does "lexicographically" means).

It's guaranteed that, with given constraints, $k$ exists and is finite.

给你两个二进制字符串 $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$ 存在且为有限值。

The first line contains a single integer $T$ ($1 \le T \le 100$) — the number of queries.

Next $2T$ lines contain a description of queries: two lines per query. The first line contains one binary string $x$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.

The second line contains one binary string $y$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.

It's guaranteed, that $1 \le f(y) \le f(x)$ (where $f(x)$ is the integer represented by $x$, and $f(y)$ is the integer represented by $y$), both representations don't have any leading zeroes, the total length of $x$ over all queries doesn't exceed $10^5$, and the total length of $y$ over all queries doesn't exceed $10^5$.

第一行包含一个整数 $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$。

Print $T$ integers (one per query). For each query print such $k$ that $rev_k$ is lexicographically minimal.

输出 $T$ 个整数（每个查询对应一个整数）。对于每个查询，输出满足 $rev_k$ 字典序最小的 $k$。

The first query was described in the legend.

In the second query, it's optimal to choose $k = 3$. The $2^3 = 1000_2$ so $s_3 = 10001_2 + 110_2 \cdot 1000_2 = 10001 + 110000 = 1000001$ and $rev_3 = 1000001$. For example, if $k = 0$, then $s_0 = 10111$ and $rev_0 = 11101$, but $rev_3 = 1000001$ is lexicographically smaller than $rev_0 = 11101$.

In the third query $s_0 = 10$ and $rev_0 = 01$. For example, $s_2 = 101$ and $rev_2 = 101$. And $01$ is lexicographically smaller than $101$.

The quote from Wikipedia: "To determine which of two strings of characters comes when arranging in lexicographical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order."

第一个查询已在题面描述中说明。

在第二个查询中，选择 $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$。

引自维基百科：“要确定两个字符串在字典序排列中哪个排在前面，需逐位比较它们的字符：首先比较首字符，若不同，则首字符在字母表中更靠前的字符串排在前面；若首字符相同，则继续比较第二字符，依此类推；若比较至某一位置时，一个字符串已无更多字符可比较而另一个仍有，则较短的字符串被认为在字典序中排在前面。”