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.

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 Specification

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

Note that the total number of cards in your deck is the sum of all ~N_i~s.

Output Specification

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.

Limits

Time limit: 45 seconds.

Memory limit: 1 GB.

~1 \le T \le 100~.

~1 \le M \le 95~. (Note that there are exactly ~95~ distinct primes between ~2~ and ~499~)

~2 \le P_i \le 499~, for all ~i~.

Each ~P_i~ is prime.

~P_i < P_{i+1}~, for all ~i~. (The primes are given in strictly increasing order)

~1 \le N_i~, for all ~i~.

Test Set 1

~2 \le N_1 + N_2 + \cdots + N_M \le 10~.

Test Set 2

~2 \le N_1 + N_2 + \cdots + N_M \le 100~.

Test Set 3

~2 \le N_1 + N_2 + \cdots + N_M \le 10^{15}~.

Sample Input

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

Sample Output

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.