Sum of Consecutive Primes

No attempts yetTime limit2sMemory limit128 MB

Problem

You are given mm integers n1,n2,,nmn_1, n_2, \dots, n_m.

A prime pp can be written as a "sum of kk consecutive primes" if there exist kk consecutive primes in the ascending list of all primes whose sum is exactly pp.

Write a program that finds the smallest prime that can, at the same time, be written as a sum of nin_i consecutive primes for every given nin_i.

For example, if m=2m = 2, n1=3n_1 = 3, and n2=5n_2 = 5, the answer is 8383. It can be written as the sum of 33 consecutive primes 23+29+3123 + 29 + 31 and also as the sum of 55 consecutive primes 11+13+17+19+2311 + 13 + 17 + 19 + 23, and it is the smallest prime that satisfies both conditions.

Input

The first line contains the number of test cases TT.

Each test case consists of two lines. The first line contains an integer mm (1m101 \le m \le 10), and the second line contains mm space-separated integers n1,n2,,nmn_1, n_2, \dots, n_m (1ni1041 \le n_i \le 10^4).

In every test case the answer is guaranteed to be smaller than 10710^7.

Output

For each test case, print Scenario i: on the first line, where ii is the 11-based test case number, and print the answer prime on the second line.

Separate the outputs of consecutive test cases with a single blank line.