소수 시간

Prime Time이라는 새로운 솔리테어 게임을 하고 있다. 카드 한 벌이 주어지며, 각 카드에는 소수가 하나 적혀 있다. 여러 카드에 같은 수가 적혀 있을 수도 있다.

목표는 첫 번째 그룹에 있는 수들의 합이 두 번째 그룹에 있는 수들의 곱과 같도록 카드를 두 그룹으로 나누는 것이다. 각 카드는 정확히 두 그룹 중 하나에 속해야 하며, 각 그룹에는 적어도 한 장의 카드가 있어야 한다. 카드 한 장으로만 이루어진 그룹의 합이나 곱은 단순히 그 카드에 적힌 수이다.

예를 들어 위 이미지에서 왼쪽 그룹의 카드에 적힌 수들의 합은 $25$이고, 오른쪽 그룹의 카드에 적힌 수들의 곱은 $25$이다. 따라서 이는 그룹을 유효하게 나눈 것이다.

점수는 첫 번째 그룹에 있는 수들의 합(두 번째 그룹에 있는 수들의 곱과 같다)이며, 이러한 방식으로 카드를 전혀 나눌 수 없다면 0이다. 얻을 수 있는 최대 점수는 얼마인가?

제한

시간 제한: 45초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{M} \le 95$. (2와 499 사이에는 서로 다른 소수가 정확히 95개 있다는 점에 유의하라.) 모든 $i$에 대해 $2 \le \mathbf{P_i} \le 499$. 각 $\mathbf{P_i}$는 소수이다. 모든 $i$에 대해 $\mathbf{P_i} \lt \mathbf{P_{i+1}}$. (소수들은 엄격한 오름차순으로 주어진다.) 모든 $i$에 대해 $1 \le \mathbf{N_i}$.

테스트 세트 1 (Visible Verdict)

$2 \le \mathbf{N_1} + \mathbf{N_2} + \cdots + \mathbf{N_M} \le 10$.

테스트 세트 2 (Visible Verdict)

$2 \le \mathbf{N_1} + \mathbf{N_2} + \cdots + \mathbf{N_M} \le 100$.

테스트 세트 3 (Hidden Verdict)

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

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 카드 한 벌에 있는 서로 다른 소수의 개수를 나타내는 하나의 정수 $\mathbf{M}$이 주어진다. 이어지는 $\mathbf{M}$개의 각 줄에는 두 값 $\mathbf{P_i}$와 $\mathbf{N_i}$이 주어지며, 이는 소수 $\mathbf{P_i}$가 적힌 카드가 정확히 $\mathbf{N_i}$장 있음을 나타낸다.

카드 한 벌에 있는 카드의 총개수는 모든 $\mathbf{N_i}$의 합이라는 점에 유의하라.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 얻을 수 있는 최대 점수이다.

예제 케이스 #1에서 최적의 분할은 $11+2+7+3+2=5\cdot5$이다. $5+7+3+2+5=11\cdot2$이라는 다른 분할도 가능하지만, 더 낮은 점수를 준다.

예제 케이스 #2에서는 같은 수가 적힌 카드들을 서로 다른 그룹에 놓을 수 있다는 점에 유의하라.