P17811 [ICPC 2019 Nanchang R] Powers of Two

Andrew has noticed that $7$ and $9$ are quite unusual digits. There are small powers of two that start with $1$ in decimal notation ($2^0 = 1$), with $2$ ($2^1 = 2$), ..., with $6$ ($2^6 = 64$), and with $8$ ($2^3 = 8$). However, the smallest power of $2$ that starts with $7$ in decimal notation is the enormous $2^{46} = 70,368,744,177,664$, and the smallest power of $2$ that starts with $9$ is even bigger: $2^{53} = 9,007,199,254,740,992$. Having learned this, Andrew wants to study the powers of two a bit more. More precisely, he will generate a number $p$ and present a positive integer $k$, and ask you: what is the $k$-th smallest power of two that starts with $p$ in decimal notation? Prepare for answering such requests! Note that it's possible to prove that there exist arbitrarily many powers of two that start with any given prefix.

The input will contain one positive integer $p$ with at most $30$ digits without leading zeroes, and a positive integer $k$ up to $70000$.

Output the $k$-th smallest non-negative integer $r$ such that $2^r$ starts with $p$ in decimal notation.

To solve this problem, you may need the logarithm of $10$ to the base of the mathematical constant $e$. Here it is in decimal notation with $503$ decimal places after the decimal point: :::align{center}  :::