Page not loading? Try clicking here.
Placeholder

#10396

Prime Time 45s 1024MB

Problems

You are playing a new solitaire game called Prime Time. You are given a deck of cards, and each card has a prime number written on it. Multiple cards may have the same number.

Your goal is to divide the cards into two groups in such a way that the sum of the numbers in the first group is equal to the product of the numbers in the second group. Each card must belong to exactly one of the two groups, and each group must contain at least one card. The sum or product of a group that consists of a single card is simply the number on that card.

Sample Case #1

For example, in the image above, the left group has cards whose sum is 25 and the right group has cards whose product is 25. Therefore, this is a valid split into groups.

Your score is the sum of the numbers in the first group (which is equal to the product of the numbers in the second group), or 0 if you cannot split the cards this way at all. What is the maximum score you can achieve?


Input

The first line of the input gives the number of test cases, \mathbf{T}. \mathbf{T} test cases follow. The first line of each test case contains a single integer \mathbf{M}, representing the number of distinct prime numbers in your deck. Each of the next \mathbf{M} lines contains two values: \mathbf{P_i} and \mathbf{N_i}, representing that you have exactly \mathbf{N_i} cards with the prime \mathbf{P_i} written on them.

Note that the total number of cards in your deck is the sum of all \mathbf{N_i}s.


Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum score you can achieve.


Example 

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
In Sample Case #1, the optimal split is: 11+2+7+3+2=5\cdot5. Another split is also possible: 5+7+3+2+5=11\cdot2, but it gives a lower score. In Sample Case #2, note that cards with the same number can be placed in different groups.

Source

GCJ 2021r1a B

You must sign in to write code.