题目描述

Bucket 计划乘坐巴士进行长途乡村旅行。她的旅行包括 $N$ 条巴士路线，按她必须乘坐的顺序编号为 $1$ 到 $N$。巴士本身速度很快，但运行频率不高。第 $i$ 条巴士路线每 $X_i$ 天才运行一次。

更具体地说，她只能在第 $X_i$、$2X_i$、$3X_i$ 等天数乘坐第 $i$ 条巴士。由于巴士速度很快，她可以在同一天乘坐多辆巴士。

Bucket 必须在第 $D$ 天之前（含第 $D$ 天）完成她的旅程，但她希望尽可能晚地开始旅程。她能够乘坐第一辆巴士的最晚天数是多少，同时仍然能在第 $D$ 天之前完成旅程？

保证 Bucket 有可能在第 $D$ 天之前完成她的旅程。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $D$。随后一行包含 $N$ 个整数，其中第 $i$ 个整数是 $X_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是她能乘坐第一辆巴士的最晚天数，同时仍能在第 $D$ 天之前完成旅程。

3
3 10
3 7 2
4 100
11 10 5 50
1 1
1

Case #1: 6
Case #2: 99
Case #3: 1

提示

在样例 #1 中，有 $N = 3$ 条巴士路线，Bucket 必须在第 $D = 10$ 天之前到达。她可以：

• 在第 $6$ 天乘坐第 $1$ 条巴士（$X_1 = 3$），
• 在第 $7$ 天乘坐第 $2$ 条巴士（$X_2 = 7$），
• 在第 $8$ 天乘坐第 $3$ 条巴士（$X_3 = 2$）。

在样例 #2 中，有 $N = 4$ 条巴士路线，Bucket 必须在第 $D = 100$ 天之前到达。她可以：

• 在第 $99$ 天乘坐第 $1$ 条巴士（$X_1 = 11$），
• 在第 $100$ 天乘坐第 $2$ 条巴士（$X_2 = 10$），
• 在第 $100$ 天乘坐第 $3$ 条巴士（$X_3 = 5$），
• 在第 $100$ 天乘坐第 $4$ 条巴士（$X_4 = 50$）。

在样例 #3 中，有 $N = 1$ 条巴士路线，Bucket 必须在第 $D = 1$ 天之前到达。她可以：

• 在第 $1$ 天乘坐第 $1$ 条巴士（$X_1 = 1$）。

限制条件

$1 \le T \le 100$。

$1 \le X_i \le D$。

$1 \le N \le 1000$。

保证 Bucket 有可能在第 $D$ 天之前完成她的旅程。

测试集 1

$1 \le D \le 100$。

测试集 2

$1 \le D \le 10^{12}$。

翻译由 DeepSeek V4 Pro 完成