32791번 - Exact Change 다국어

문제

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.

입력

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

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

출력

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

제한

힌트