All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/DEC19/hindi/BINADD.pdf), [Bengali](http://www.codechef.com/download/translated/DEC19/bengali/BINADD.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/DEC19/mandarin/BINADD.pdf), [Russian](http://www.codechef.com/download/translated/DEC19/russian/BINADD.pdf), and [Vietnamese](http://www.codechef.com/download/translated/DEC19/vietnamese/BINADD.pdf) as well. Recently, Chef studied the [binary numeral system](https://en.wikipedia.org/wiki/Binary_number) and noticed that it is extremely simple to perform bitwise operations like [AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND), [XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) or [bit shift](https://en.wikipedia.org/wiki/Bitwise_operation#Bit_shifts) on non-negative integers, while it is much more complicated to perform arithmetic operations (e.g. addition, multiplication or division). After playing with binary operations for a while, Chef invented an interesting algorithm for addition of two non-negative integers $A$ and $B$: ``` function add(A, B): while B is greater than 0: U = A XOR B V = A AND B A = U B = V * 2 return A ``` Now Chef is wondering how fast this algorithm is. Given the initial values of $A$ and $B$ (in binary representation), he needs you to help him compute the number of times the while-loop of the algorithm is repeated. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains a single string $A$. - The second line contains a single string $B$. ### Output For each test case, print a single line containing one integer ― the number of iterations the algorithm will perform during addition of the given numbers $A$ and $B$. ### Constraints - $1 \le T \le 10^5$ - $1 \le |A|, |B| \le 10^5$ - $A$ and $B$ contain only characters '0' and '1' - the sum of $|A| + |B|$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (20 points):** $|A|, |B| \le 30$ **Subtask #2 (30 points):** - $|A|, |B| \le 500$ - the sum of $|A| + |B|$ over all test cases does not exceed $10^5$ **Subtask #3 (50 points):** original constraints ### Example Input ``` 3 100010 0 0 100010 11100 1010 ``` ### Example Output ``` 0 1 3 ``` ### Explanation **Example case 1:** The initial value of $B$ is $0$, so while-loop is not performed at all. **Example case 2:** The initial values of $A$ and $B$ are $0_2 = 0$ and $100010_2 = 34$ respectively. When the while-loop is performed for the first time, we have: - $U = 34$ - $V = 0$ - $A$ changes to $34$ - $B$ changes to $2 \cdot 0 = 0$ The while-loop terminates immediately afterwards, so it is executed only once. **Example case 3:** The initial values of $A$ and $B$ are $11100_2 = 28$ and $1010_2 = 10$ respectively. After the first iteration, their values change to $22$ and $16$ respectively. After the second iteration, they change to $6$ and $32$, and finally, after the third iteration, to $38$ and $0$.
|Tags||alex_2oo8, bignum, binary, dec19, easy, melfice|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.