A12838 | $You Are Given Two Binary Strings...$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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.

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$ .

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

输入 #1

4
1010
11
10001
110
1
1
1010101010101
11110000

输出 #1

C++ 编辑器

输入

输出