무당벌레 리사와 고장 난 계산기

무당벌레 리사(Lisa)는 수학을 좋아합니다. 오늘 리사는 지네 교수 칼큘론(Calculon)의 시험을 봅니다. 시험에서는 계산기 화면에 정해진 수 $N$을 띄워야 하며, 점수는 그 수를 만들기 위해 누른 키의 개수로 정해집니다. 만점을 원하는 리사는 $N$을 화면에 띄우는 가장 짧은 키 입력 순서를 찾아야 합니다.

이 계산기는 아주 낡아서 일부 키만 동작합니다. 동작하는 키는 다음 집합의 부분집합입니다.

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

0부터 9까지는 숫자 버튼, =는 등호 버튼, 나머지 + - * /는 연산자 버튼입니다. (초기화용 C 키는 이 문제에서 다루지 않습니다.)

계산기는 세 개의 내부 레지스터를 가집니다.

• disp: 현재 화면에 표시된 값
• op: 마지막으로 누른 연산자 또는 등호 (처음에는 =)
• value: 저장된 값 (처음에는 $0$)

두 값에 대한 연산 결과는 $\mathrm{eval}(a, \mathrm{op}, b)$로 나타냅니다. 예를 들어 $\mathrm{op}$가 +이면 $a + b$입니다. 나눗셈은 항상 내림하여 $\lfloor a / b \rfloor$가 됩니다.

처음에 화면에는 $0$이 표시되어 있고, value는 $0$, op는 =입니다. 각 키를 누르면 다음과 같이 동작합니다.

• 숫자 버튼 d: 숫자를 입력하던 중이었다면 뒤에 이어 붙입니다. 즉 disp $\leftarrow$ disp $\times 10 + d$. 직전에 연산자나 등호를 눌렀거나 맨 처음이라면 새 수를 시작합니다. 즉 disp $\leftarrow d$.
• 연산자 버튼(+ - * /): 방금 숫자를 입력한 뒤라면 먼저 대기 중이던 연산을 계산합니다. value $\leftarrow$ disp $\leftarrow \mathrm{eval}(\text{value}, \text{op}, \text{disp})$. 그다음 op를 새 연산자로 바꿉니다. (맨 처음에는 op가 =이고 $\mathrm{eval}(a, \texttt{=}, b) = b$이므로, 처음 입력한 수가 그대로 value가 됩니다.) 반면 마지막 연산자·등호 이후로 새 숫자를 입력하지 않았다면, op만 새 연산자로 바뀝니다. (연산자 버튼을 연달아 누르면 마지막 것만 누른 것과 같습니다.)
• 등호 버튼 =: 방금 숫자를 입력한 뒤라면 연산자 버튼처럼 대기 중이던 연산을 계산한 뒤 op를 =로 둡니다. 연산자 버튼 바로 뒤에 눌렀다면 그 연산을 같은 두 피연산자로 계산합니다. 즉 value $\leftarrow$ disp $\leftarrow \mathrm{eval}(\text{value}, \text{op}, \text{value})$. 등호를 두 번 이상 연달아 누르는 것은 한 번 누른 것과 같습니다.

다음 규칙도 유의하세요.

• 화면에는 $[0, 999]$ 범위의 정수만 표시할 수 있습니다. 시험 도중 어느 순간에라도 이 범위를 벗어난 값이 나오면 오류가 나 시험에 실패합니다.
• 나눗셈 결과는 항상 내림하여 정수가 됩니다. ($0$으로 나누는 것은 허용되지 않습니다.)

예를 들어, 사용할 수 있는 버튼이 2 3 + / =이고 목표가 $7$일 때, 2 2 / 3 +와 2 2 / 3 /는 길이 $5$의 최적 해 중 하나입니다. 3 + 2 + 2 +도 답이 되지만 더 깁니다. 또, 사용할 수 있는 버튼이 3 2 = +이고 목표가 $7$일 때는 3 + 2 + 2 +와 2 + = + 3 +가 최적 해 중 하나입니다.

처음 화면에 $0$이 표시되어 있으므로, $N = 0$은 키를 하나도 누르지 않아도 됩니다.

입력의 각 줄은 하나의 질의를 나타냅니다. 각 줄은 사용할 수 있는 버튼들의 비어 있지 않은 문자열(허용된 집합의 문자들로만 이루어지며 공백이 없음)로 시작하고, 이어서 공백 하나와 화면에 띄워야 할 정수 $N$ ($0 \le N \le 999$)이 옵니다. 입력은 파일의 끝에서 종료됩니다.

각 질의마다, 화면에 $N$을 띄우는 가장 짧은 버튼 입력 순서의 길이를 한 줄에 출력합니다. 불가능하면 impossible을 출력합니다.