Description

你正在玩一款名为质数时刻的新单人纸牌游戏。你有一副卡牌，每张牌上写有一个质数，不同牌可能写有相同的数字。

游戏目标是将所有卡牌分成两组：第一组卡牌上的数字之和等于第二组卡牌上的数字之积。每张牌必须属于其中一组，且每组至少包含一张牌。若某组仅有一张牌，则该组的和或积即为该牌上的数字。

例如上图中，左侧卡牌数字之和为 $25$，右侧卡牌数字之积也为 $25$，因此这是一个有效的分组方案。

你的得分等于第一组数字之和（即第二组数字之积），若无法完成这样的分组则得分为 $0$。你能获得的最高得分是多少？

Input Format

输入第一行包含测试用例数量 $\mathbf{T}$。随后每个测试用例包含：

• 第一行：整数 $\mathbf{M}$，表示牌堆中不同质数的种类数
• 接下来 $\mathbf{M}$ 行：每行两个数 $\mathbf{P}_i$ 和 $\mathbf{N}_i$，表示有 $\mathbf{N}_i$ 张数字为 $\mathbf{P}_i$ 的卡牌

注意牌堆总卡牌数为所有 $\mathbf{N}_i$ 之和。

Output Format

对每个测试用例，输出 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为可获得的最大得分。

4
5
2 2
3 1
5 2
7 1
11 1
1
17 2
2
2 2
3 1
1
2 7

Case #1: 25
Case #2: 17
Case #3: 0
Case #4: 8

Hint

样例解释

在样例 #1 中，最优分组为 $11 + 2 + 7 + 3 + 2 = 5 \cdot 5$。另一可行分组 $5 + 7 + 3 + 2 + 5 = 11 \cdot 2$ 得分较低。

在样例 #2 中，注意相同数字的卡牌可以分到不同组。

数据范围

• $1 \leq \mathbf{T} \leq 100$
• $1 \leq \mathbf{M} \leq 95$（在 2 至 499 之间的质数共 95 个）
• $2 \leq \mathbf{P}_i \leq 499$（均为质数）
• $\mathbf{P}_i < \mathbf{P}_{i+1}$（质数按严格递增顺序给出）
• $1 \leq \mathbf{N}_i$

测试集 1（7 分，可见判定）

• 总卡牌数 $2 \leq \sum \mathbf{N}_i \leq 10$

测试集 2（13 分，可见判定）

• 总卡牌数 $2 \leq \sum \mathbf{N}_i \leq 100$

测试集 3（15 分，隐藏判定）

• 总卡牌数 $2 \leq \sum \mathbf{N}_i \leq 10^{15}$

翻译由 DeepSeek V3 完成