给定两个二进制字符串 $$$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$$$ 按字典顺序最小。
示例
输入 #1
4 1010 11 10001 110 1 1 1010101010101 11110000
输出 #1
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$$$。
引用自维基百科:“要确定按字典顺序排列时出现两个字符串中的哪一个,请比较它们的第一个字母。如果它们不同,则第一个字母在字母表中出现较早的字符串位于另一个字符串之前。如果第一个字母相同,则比较第二个字母,依此类推。如果到达一个位置,一个字符串没有更多字母可供比较,而另一个字符串则有,则认为第一个(较短的)字符串按字母顺序排在第一位。”