고장 난 계산기 (Small)

앨리스는 수학을 아주 잘하는 학생이다. 지금 수학 수업을 듣고 있는데, 선생님이 계산기 사용법을 가르치고 있다. 선생님이 정수 하나를 부르면 학생은 그 수를 계산기에 그대로 입력해야 한다. 입력하지 못한 학생은 이렇게 쉬운 일을 해내지 못했다는 이유로 벌을 받는다.

수업이 시작될 때 앨리스는 자기 계산기가 고장 났다는 사실을 알아차렸다. 숫자 버튼 중 몇 개는 아예 눌리지 않고, 연산 버튼은 곱하기와 등호만 살아 있다. 앨리스는 살아 있는 버튼만으로 선생님이 부른 수를 만들어야 한다.

앨리스가 입력하는 식의 형태는 이렇다. 먼저 수를 하나 입력하고, 필요하면 곱하기를 누른 뒤 수를 하나 더 입력하는 과정을 원하는 만큼 반복한 다음, 마지막에 등호를 누른다. 입력하는 각 수는 살아 있는 숫자 버튼만으로 이루어져야 하고, 맨 앞자리가 0이면 안 된다. 입력한 수를 모두 곱한 값은 선생님이 부른 수 $X$와 정확히 같아야 한다. 버튼을 누른 총 횟수는 입력한 수의 자릿수 합에 곱하기를 누른 횟수를 더하고, 마지막 등호 한 번을 더한 값이다.

선생님이 60을 부르고 앨리스가 누를 수 있는 숫자가 1, 2, 5뿐이라고 하자. 15*2*2=를 입력하면 자릿수 합이 4, 곱하기가 2번, 등호가 1번이므로 모두 7번을 눌러야 한다. 12*5=를 입력하면 5번이면 된다.

앨리스는 버튼을 누르는 횟수를 최소로 하고 싶다. 그 최솟값을 구하라.

첫째 줄에 선생님이 부르는 정수의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄이다. 첫째 줄에는 0 또는 1인 수 열 개가 주어진다. 0번부터 세어 $i$번째 수가 1이면 숫자 $i$ 버튼을 누를 수 있고, 0이면 고장 난 것이다. 둘째 줄에는 선생님이 부른 정수 $X$가 주어진다.

제한

• $1 \le T \le 100$
• $1 \le X \le 10^6$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 필요한 최소 버튼 클릭 수다. $X$를 만들 수 없으면 $y$ 자리에 Impossible을 출력한다.

곱하기 없이 수 하나만 입력하는 경우에도 마지막 등호는 반드시 눌러야 한다. 숫자 버튼이 모두 살아 있고 $X$가 128이면 1, 2, 8과 등호를 눌러 4번이 된다.

살아 있는 버튼만으로는 곱해서 $X$가 되는 수를 하나도 만들지 못하는 경우가 있다. 홀수 버튼만 살아 있으면 어떤 수를 곱해도 결과가 홀수이므로 128은 만들 수 없다.