你正在玩一种名为 Prime Time 的新纸牌游戏。你有一副牌，每张牌上都写有一个质数。多张牌上可能写有相同的数字。

你的目标是将这些牌分成两组，使得第一组中数字的和等于第二组中数字的积。每张牌必须恰好属于其中一组，且每组必须至少包含一张牌。如果一组只有一张牌，那么该组的和或积就是这张牌上的数字。

例如，在上图中，左侧一组牌的和为 25，右侧一组牌的积为 25。因此，这是一种有效的分组方式。

你的得分是第一组中数字的和（这等于第二组中数字的积），如果你无法以这种方式拆分牌，则得分为 0。你能获得的最高得分是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $M$，表示牌堆中不同质数的数量。接下来的 $M$ 行，每行包含两个值 $P_i$ 和 $N_i$，表示你有 $N_i$ 张写有质数 $P_i$ 的牌。

注意，牌堆中的总牌数为所有 $N_i$ 之和。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是你能获得的最高得分。

数据范围

$1 \le T \le 100$。 $1 \le M \le 95$（注意 2 到 499 之间恰好有 95 个不同的质数）。 $2 \le P_i \le 499$，对于所有 $i$。 每个 $P_i$ 均为质数。 $P_i < P_{i+1}$，对于所有 $i$（质数按严格递增顺序给出）。 $1 \le N_i$，对于所有 $i$。

子任务

测试集 1（可见判决） $2 \le N_1 + N_2 + \dots + N_M \le 10$。

测试集 2（可见判决） $2 \le N_1 + N_2 + \dots + N_M \le 100$。

测试集 3（隐藏判决） $2 \le N_1 + N_2 + \dots + N_M \le 10^{15}$。

样例

样例输入 1

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

样例输出 1

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

说明

在样例 1 中，最优拆分方式为：$11 + 2 + 7 + 3 + 2 = 5 \cdot 5$。另一种可能的拆分方式为：$5 + 7 + 3 + 2 + 5 = 11 \cdot 2$，但其得分较低。

在样例 2 中，请注意写有相同数字的牌可以被放置在不同的组中。