고장 난 계산기 (라지)

앨리스는 수학을 잘하는 학생이고 지금 수학 수업을 듣고 있다. 선생님이 정수 하나를 말하면 학생은 그 수를 계산기에 그대로 입력해야 한다. 입력하지 못한 학생은 벌을 받는다.

수업이 시작될 때 앨리스는 자기 계산기가 고장 난 것을 알아차렸다. 숫자 버튼 중 몇 개는 아예 눌리지 않고, 그 밖에 쓸 수 있는 버튼은 곱하기와 등호뿐이다. 앨리스는 살아 있는 숫자 버튼과 곱하기, 등호만으로 그 수를 만들어야 한다.

앨리스는 수를 하나씩 입력하면서 그 사이마다 곱하기를 누르고, 마지막에 등호를 한 번 누른다. 입력하는 수는 앞에 0을 붙이지 않은 보통의 십진 표기여야 하고, 그 수의 모든 자리 숫자가 살아 있는 버튼이어야 한다. 수를 입력하는 데는 자리 수만큼 클릭이 들고, 곱하기를 한 번 누를 때마다 클릭이 하나, 마지막 등호에 클릭이 하나 든다. 입력한 수를 모두 곱한 값은 선생님이 말한 수와 같아야 한다.

선생님이 60을 말했고 버튼 1, 2, 5만 살아 있다고 하자. 앨리스는 1522= 를 눌러 만들 수 있고, 클릭은 15에 두 번, 곱하기에 한 번, 2에 한 번, 곱하기에 한 번, 2에 한 번, 등호에 한 번으로 모두 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을 출력한다.

버튼 1, 2, 5만 살아 있을 때 60은 12*5= 로 5번 만에 만들 수 있다. 모든 숫자 버튼이 살아 있으면 128은 숫자 세 번과 등호 한 번으로 4번이면 된다. 곱셈을 하지 않아도 등호는 눌러야 한다. 1, 3, 5, 7, 9만 살아 있으면 입력할 수 있는 수가 모두 홀수여서 그 곱도 홀수이므로 128은 만들 수 없다.