Broken Calculator (Large)

Alice is good at math and she is sitting in a math class. The teacher says an integer out loud, and every student has to type that exact number into a calculator. A student who fails to type it is punished.

At the start of the class Alice notices that her calculator is broken. Some of the digit buttons do not respond at all, and the only other buttons that still work are multiply and equals. She has to reach the number with the working digit buttons, the multiply button and the equals button.

Alice types one number after another, presses multiply between them, and presses equals once at the end. Every number she types is written in ordinary decimal form with no leading zeros, and each of its digits must be a working button. Typing a number costs one click per digit, each multiply press costs one click, and the final equals press costs one click. The product of the typed numbers must equal the number the teacher said.

Suppose the teacher says 60 and only the buttons 1, 2 and 5 work. Alice can press 1522=, which costs 7 clicks: two on 15, one on multiply, one on 2, one on multiply, one on 2 and one on equals. Pressing 12*5= costs only 5 clicks. Alice wants the number of clicks to be as small as possible.

Given the working buttons and the number the teacher said, find the minimum number of clicks.

The first line contains $T$, the number of integers the teacher says. $T$ test cases follow.

Each test case is two lines. The first line contains ten values separated by spaces, each of them 0 or 1. Counting from 0, the $i$-th value is 1 if the button for digit $i$ works and 0 if it is broken. The second line contains one integer $X$, the number the teacher said.

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

For each test case print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the minimum number of clicks. If Alice cannot produce $X$ at all, print Impossible in place of y.

With only the buttons 1, 2 and 5 working, 60 takes 5 clicks as 12*5=. When every digit button works, 128 takes 4 clicks: three digit clicks and one equals click. Alice still presses equals when she multiplies nothing. When only 1, 3, 5, 7 and 9 work, every number she can type is odd, so every product is odd and 128 is out of reach.