题目描述

Alice 是一位聪明的学生，数学非常好。她正在上一堂数学课。在这堂课上，老师正在教学生们如何使用计算器。老师会告诉所有学生一个整数，学生们必须在自己的计算器上键入这个确切的数字。如果有人没能输入这个数字，他或她就会因未能完成如此简单的任务而受到惩罚！

不幸的是，在课堂开始时，Alice 发现她的计算器坏掉了！她发现一些数字按键完全损坏了，只有“乘号”和“等号”这两个操作键可以使用。因此，她只能利用这些按键来快速得到所需的数字。

例如，老师可能说出数字“$60$”，而 Alice 的计算器只能键入“$1$”、“$2$”和“$5$”。她可以按顺序按下以下按键：

• 按键“$15$”（需要按 $2$ 下）
• 按键“乘号”（$1$ 下）
• 按键“$2$”（$1$ 下）
• 按键“乘号”（$1$ 下）
• 按键“$2$”（$1$ 下）
• 按键“等号”（$1$ 下）

这种方法需要按 $7$ 下。然而，如果 Alice 改用“$12\times 5=$”，则只需要按 $5$ 下。当然，Alice 希望尽可能快地得到这个整数，因此她想最小化按键的总次数。你的任务是帮助她找到一种快速得到所需数字的方法。

输入格式

输入的第一行给出一个整数 $T$，表示老师给出的数字的数量。接下来是 $T$ 个测试用例。

每个测试用例包含两行。第一行包含十个数字，每个数字只有 $0$ 或 $1$。第 $i$ 个数字（从 $0$ 开始）若为“$1$”，则表示数字 $i$ 可以被点击；若为“$0$”，则表示该按键已损坏。第二行仅包含一个整数 $\mathbf{X}$，即老师告诉所有人的那个整数。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所需的最少按键次数，如果无法生成该数字，则 $y$ 为 Impossible。

3
0 1 1 0 0 1 0 0 0 0
60
1 1 1 1 1 1 1 1 1 1
128
0 1 0 1 0 1 0 1 0 1
128

Case #1: 5
Case #2: 4
Case #3: Impossible

提示

第一个样例在题目描述中已作解释。

在第二个样例中，所有数字均可使用，因此 Alice 只需依次按下“$1$”、“$2$”、“$8$”和“等号”即可得到结果。请注意，即使没有进行运算，最后一步仍然需要按下“等号”。

对于最后一个样例，由于 Alice 无法输入任何偶数，这是不可能的。

限制

$1 \le T \le 100$。

小数据集（测试集 1 - 可见）

$1 \le X \le 100$。

大数据集（测试集 2 - 隐藏）

$1 \le X \le 10^6$。

翻译由 DeepSeek V4 Pro 完成