고장 난 계산기

Alice는 수학을 매우 잘하는 똑똑한 학생이다. Alice는 수학 수업에 참여하고 있다. 이 수업에서 선생님은 학생들에게 계산기 사용법을 가르치고 있다. 선생님은 모든 학생에게 정수 하나를 말하고, 학생들은 그 정확한 수를 자신의 계산기에 입력해야 한다. 누군가 그 수를 입력하지 못하면, 그렇게 쉬운 과제를 실패한 벌을 받게 된다!

안타깝게도 수업이 시작될 때 Alice는 자신의 계산기가 고장 났다는 것을 알게 된다! 숫자 버튼 중 일부는 완전히 고장 났고, 연산자 버튼 중에서는 "곱하기"와 "등호"만 사용할 수 있다는 것을 발견한다. 따라서 Alice는 이 버튼들만 사용하여 그 수를 빠르게 만들어야 한다.

예를 들어 선생님이 "60"을 말했지만, Alice의 계산기에서는 "1", "2", "5"만 입력할 수 있다고 하자. Alice는 다음 버튼들을 누를 수 있다.

• "15" 버튼 (2번 누름)

• "곱하기" 버튼 (1번 누름)

• "2" 버튼 (1번 누름)

• "곱하기" 버튼 (1번 누름)

• "2" 버튼 (1번 누름)

• "등호" 버튼 (1번 누름)

이 방법은 버튼을 7번 눌러야 한다. 그러나 Alice가 "12*5="을 사용하면 5번만 누르면 된다. 물론 Alice는 가능한 한 빨리 그 정수를 만들고 싶으므로, 버튼을 누르는 횟수를 최소화하고자 한다. Alice가 필요한 수를 빠르게 만드는 방법을 찾도록 도와주는 것이 여러분의 과제이다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ X ≤ 100.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ X ≤ $10^{6}$.

입력의 첫 번째 줄에는 선생님이 말하는 정수의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫 번째 줄에는 각각 0 또는 1만 가능한 수 열 개가 주어진다. 0부터 시작하는 i번째 수는 숫자 i를 누를 수 있으면 "1"이고, 고장 났으면 "0"이다. 두 번째 줄에는 선생님이 모두에게 말한 정수인 수 X 하나만 주어진다.

각 테스트 케이스마다 "Case #x: y"를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 필요한 최소 버튼 누름 횟수이다. 그 수를 만들 수 없다면 "Impossible"을 출력한다.

첫 번째 예제 케이스는 문제 설명에 설명되어 있다.

두 번째 케이스에서는 모든 숫자를 사용할 수 있으므로, Alice는 "1", "2", "8"을 누른 다음 "등호"를 눌러 결과를 얻을 수 있다. 계산이 없더라도 마지막 단계에서 여전히 "등호"를 눌러야 한다는 점에 유의하라.

마지막 케이스에서는 Alice가 어떤 짝수도 입력할 수 없으므로 불가능하다.