Exact Change

Time limit1sMemory limit2048 MB

Summary

Given binary numbers a and b with up to 10^6 bits, find the fewest powers-of-two coins that let you pay every integer amount from a to b exactly.

Level: Medium7 of 10
Topics: Math, Greedy, Bit manipulation
Solved: No attempts yet

Statement

While in Binaria, you find a store where you want to buy some presents for your friends. In Binaria, the currency is bits, and the coin denominations are the set of all integer powers of $2$ . You know that you want to spend at least $a$ bits here, but no more than $b$ bits.

When you make a purchase, you must pay with exact change. You have an unlimited number of bits that you can access from your bank account, but you can choose to withdraw them in whatever denominations you find most convenient. Carrying many coins is inconvenient though, so you wish to minimize the number of coins you carry with you.

Compute the minimum number of coins you need to bring with you such that you can pay any integer amount of bits between $a$ and $b$ , inclusive.

Input

The first line of input contains a single integer $a$ , $1 \le a < 2^{1000000}$ . $a$ is written in base 2 with no leading zeros.

The second line of input contains a single integer $b$ , $a \le b < 2^{1000000}$ . $b$ is written in base 2 with no leading zeros.

Output

Output a single integer $k$ , the minimum number of coins you need to bring.

Examples2

Example 1
Input
```
10101
101010
```
Expected output
```
6
```
Example 2
Input
```
100
101
```
Expected output
```
2
```