Sunny wants to buy a diamond necklace from a jewellery shop to celebrate Christmas. In the jewellery shop, each diamond has a number on it, either $0$ or $1$. The jewellery shop owner asks him to choose a subsequence of diamonds from a binary string $S$ to make his necklace. Note that a subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Sunny wants his necklace to be beautiful, he thinks a necklace is beautiful if it makes up a binary number less than or equal to $K$. Can you help Sunny to find the length of the longest beautiful necklace?

Input

The first line of the input contains 1 binary string $S$.
The second line of the input contains 1 integer $K$.

Output

Output 1 integer, the length of the longest beautiful necklace.

Subtasks

For all cases, $1\le|S|\le10^5, 1\le K\lt 2^{63}$.
Subtask 1 (21%): $K\le 1$
Subtask 2 (38%): $|S| \le 1000$
Subtask 3 (41%): No additional constraints