Broken Calculator (Small)

Alice is a student who is very good at math. She is in a math class where the teacher is showing everyone how to use a calculator. The teacher calls out an integer, and each student has to type that exact number into their calculator. A student who fails to type it is punished for missing such an easy task.

At the start of the class Alice notices that her calculator is broken. Some of the digit buttons do not respond at all, and among the operator buttons only multiply and equals still work. Alice has to produce the number the teacher called out using only the buttons that still work.

The expression Alice types has this shape. She types a number, then optionally presses multiply and types another number, repeating that as often as she likes, and finally presses equals. Every number she types must consist only of working digit buttons, and its first digit must not be 0. The product of all the numbers she types must be exactly $X$, the number the teacher called out. The total click count is the sum of the digit counts of the numbers she typed, plus the number of multiply presses, plus one for the final equals.

Suppose the teacher calls out 60 and only the digits 1, 2 and 5 work. Typing 15*2*2= costs 4 digit clicks, 2 multiply clicks and 1 equals click, so 7 clicks in total. Typing 12*5= costs only 5 clicks.

Alice wants the click count to be as small as possible. Find that minimum.

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

Each test case has two lines. The first line contains ten numbers, each 0 or 1. Counting from 0, the $i$-th number is 1 if the digit $i$ button can be pressed and 0 if it is broken. The second line contains $X$, the integer the teacher called out.

Limits

• $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 button clicks. If $X$ cannot be produced, print Impossible in place of $y$.

Alice presses equals even when she types a single number and no multiplication happens. With every digit button working and $X$ equal to 128, she presses 1, 2, 8 and equals, which is 4 clicks.

Sometimes no product of typeable numbers equals $X$. If only the odd digit buttons work, every product is odd, so 128 cannot be produced.