题目描述

Ada 为她的朋友 John 买了一份秘密礼物。为了打开礼物，Ada 希望 John 破解一个密码。她决定给他一个提示以简化问题。她告诉他，密码是一个可以由两个连续质数的乘积构成的数，并且是小于或等于 $Z$ 的最大数。给定 $Z$ 的值，请帮助 John 确定这个密码。

形式化地，设质数的顺序 $2, 3, 5, 7, 11, \ldots$ 记为 $p_1, p_2, p_3, p_4, p_5, \ldots$，以此类推。令 $R_i$ 为两个连续质数 $p_i$ 和 $p_{i+1}$ 的乘积。密码是满足 $R_j \le Z$ 的最大 $R_j$。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行。

每行包含一个整数 $Z$，表示 Ada 作为提示一部分给出的数。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是密码——小于或等于 $Z$ 且为两个连续质数乘积的最大数。

2
2021
2020

Case #1: 2021
Case #2: 1763

提示

对于样例 #1，密码为 $2021$，因为它正好是连续质数 $43$ 和 $47$ 的乘积。

对于样例 #2，密码为 $1763$，因为 $41$ 和 $43$ 的乘积为 $1763$，小于 $2020$，而 $43$ 和 $47$ 的乘积超过了给定的 $2020$。

限制条件

$1 \le T \le 100$。

测试集 1

$6 \le Z \le 2021$。

测试集 2

$6 \le Z \le 10^9$。

测试集 3

$6 \le Z \le 10^{18}$。

翻译由 DeepSeek V4 Pro 完成