Sum of Consecutive Primes
Time limit2sMemory limit128 MB
For each query set of counts, find the smallest prime expressible as a sum of exactly n_i consecutive primes for every given n_i.
- Level
Medium6 of 10
- Topics
- Number theory, Prefix sum, Brute force, Two pointers
- Solved
- No attempts yet
Problem
You are given integers .
A prime can be written as a "sum of consecutive primes" if there exist consecutive primes in the ascending list of all primes whose sum is exactly .
Write a program that finds the smallest prime that can, at the same time, be written as a sum of consecutive primes for every given .
For example, if , , and , the answer is . It can be written as the sum of consecutive primes and also as the sum of consecutive primes , and it is the smallest prime that satisfies both conditions.
Input
The first line contains the number of test cases .
Each test case consists of two lines. The first line contains an integer (), and the second line contains space-separated integers ().
In every test case the answer is guaranteed to be smaller than .
Output
For each test case, print Scenario i: on the first line, where is the -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.