Problem Description

You are given two binary numbers $x$ and $y$ $(0 \leq y \leq x)$. $x$ is variable while $y$ is constant. You need to perform some steps of operations on $x$ and finally make $x$ equal to $y$.

In each step, you can perform one of the two operations below.


* Make $x$ become $x-1$. This operation can be performed only if $x>0$.
* If the $i$-th most significant bit of $x$ is 1, and the $i+1$-th most significant bit of $x$ is 0, we can swap the two bits in $x$. That is to say, for two adjacent bits, if the `left` is $1$ and the `right` is $0$, we can swap them (change $10$ to $01$).

Now you need to find the minimum steps we need to make $x$ become $y$.

Input

There are multiple test cases.

For each test case, there is a line containing two binary integers $x$ and $y$.

The total length of all binary integers in a test file is not larger than $2000000$.

Output

For each test case, output an integer in a line, denoting the minimum steps to make $x$ become $y$.

10100 1000
1000001 11111
10010 0
11111 101
101001 10010

4
3
7
11
4