在 Binaria，你发现了一家商店，想为朋友们买些礼物。在 Binaria，货币单位是 bits，硬币的面值是所有 2 的整数次幂。你知道你想要花费至少 $a$ bits，且不超过 $b$ bits。

当你进行购买时，必须支付准确的金额。你可以从银行账户中获取无限数量的 bits，但你可以选择以任何你认为最方便的面值提取它们。携带过多的硬币很不方便，因此你希望最小化你所携带的硬币数量。

计算你需要携带的最少硬币数量，使得你可以支付 $a$ 到 $b$（包含 $a$ 和 $b$）之间的任何整数金额。

输入格式

第一行包含一个整数 $a$，$1 \le a < 2^{1000000}$。$a$ 将以二进制形式给出，且没有前导零。 第二行包含一个整数 $b$，$a \le b < 2^{1000000}$。$b$ 将以二进制形式给出，且没有前导零。

输出格式

输出一个整数 $k$，表示你需要携带的最少硬币数量。

样例

样例输入 1

10101
101010

样例输出 1

6

样例输入 2

100
101

样例输出 2

2