Lisa the Ladybug and the Broken Calculator

Lisa the Ladybug loves mathematics. Today she is taking an exam set by her professor, Calculon the Centipede. In the exam she must make a prescribed number $N$ appear on the display of a calculator, and her score depends on how many keys she presses. Because Lisa wants a perfect score, she needs the shortest possible sequence of key presses that displays $N$.

The calculator is very old, so only some of its keys work. The working keys form a subset of:

0 1 2 3 4 5 6 7 8 9 + - * / =

Buttons 0 through 9 are the numeric buttons, = is the equals button, and the remaining + - * / are the operator buttons. (The reset key C is not considered in this problem.)

The calculator keeps three internal registers:

• disp: the value currently shown on the display
• op: the last operator or equals button pressed (initially =)
• value: a stored value (initially $0$)

The result of an operation on two values is written $\mathrm{eval}(a, \mathrm{op}, b)$; for example, if $\mathrm{op}$ is + it equals $a + b$. Division always rounds down, i.e. $\lfloor a / b \rfloor$.

At the start the display shows $0$, value is $0$, and op is =. Pressing a key behaves as follows:

• Numeric button d: if you were in the middle of typing a number, the digit is appended: disp $\leftarrow$ disp $\times 10 + d$. If instead the previous press was an operator or equals (or this is the very first press), a new number is started: disp $\leftarrow d$.
• Operator button (+ - * /): if you have just typed a number, the pending operation is first computed: value $\leftarrow$ disp $\leftarrow \mathrm{eval}(\text{value}, \text{op}, \text{disp})$, and then op becomes the new operator. (At the very beginning op is = and $\mathrm{eval}(a, \texttt{=}, b) = b$, so the first number you type simply becomes value.) If instead no new number has been typed since the last operator or equals, only op is replaced by the new operator (a run of operator buttons acts as if only the last one were pressed).
• Equals button =: if you have just typed a number, it computes the pending operation exactly like an operator button and then leaves op equal to =. If it is pressed right after an operator button, the operator is evaluated with two equal operands: value $\leftarrow$ disp $\leftarrow \mathrm{eval}(\text{value}, \text{op}, \text{value})$. Pressing equals two or more times in a row has the same effect as pressing it once.

Also note the following:

• The display can only show integers in the range $[0, 999]$. If a value outside this range is obtained at any moment during the exam, an error occurs and the exam is failed.
• The result of a division is always rounded down to an integer. (Dividing by zero is not allowed.)

For example, if the available buttons are 2 3 + / = and the target is $7$, then 2 2 / 3 + and 2 2 / 3 / are among the optimal solutions of length $5$, while 3 + 2 + 2 + is also a solution but longer. If the available buttons are 3 2 = + and the target is $7$, then 3 + 2 + 2 + and 2 + = + 3 + are among the optimal solutions.

Because the display starts at $0$, the value $N = 0$ requires no key presses at all.

Each line of the input describes one query. A line starts with a non-empty string of available buttons (made only of characters from the allowed set, with no spaces), followed by a single space and the integer $N$ ($0 \le N \le 999$) that must be shown on the display. The input ends at end of file.

For each query, print on its own line the length of the shortest sequence of buttons whose pressing makes the display show $N$. If it cannot be done, print impossible.