ARRPRM - Prime is fun


You will be given an array A. You can pick X (where X is a prime) consecutive elements from the array A so that the sum is maximized. Note that you can select multiple consecutive elements.

For example, if you are given an array with 10 elements, then one of ways you can select elements by selecting 1st, 2nd element then 4th, 5th, 6th element then 8th, 9th elements.

Another way can be to select 1st and 2nd element then select 4-10 elements.

Input

The first line of the input will be an integer t, denoting the number of the test cases.

For each test case, there will be an integer n, denoting the size of the array A.

Next line there will be n integers denoting the elements of the array A.

Output

For each test case, print the maximized sum (as discussed above) in a line.

Constraints

1 <= t <= 100

1 <= n <= 2000

1 <= elements of the array A <= 100000

Sample

Input:
2
4
1 2 3 4
10
10 1 1 1 1 1 1 2 2 2

Output:
9
21

hide comments
smso: 2021-12-02 05:43:38

more testcases:

[snip]

==(Francky)=> Please read the footer ; no hints here.

Last edit: 2021-12-03 15:44:26
akjol2049: 2018-12-04 15:05:45

can all elements be selected if n is prime?

mahilewets: 2017-09-17 10:00:51

Solved with two-dimensional dp in 0.19 sec in C++
Feel like I did some overkill

sas1905: 2017-06-06 14:35:47

@Jamil For second test case..Why can't we choose first 7 elements(1-7) and (8-10) ..This will give a sum of 10+6*1+2*3=22 which is greater than 21..

Jamil Siam: 2017-04-04 13:40:41

For those who did not understand the 2nd testcase:
for optimal answer we select first 2 elements: 10+1 = 11
then we select 4-10 elements 1+1+1+1+2+2+2 = 10
Total Answer is 21.

Hope it is clear to everyone now!

sdeven_0245: 2017-04-03 05:01:52

@jamil please explain the second test case

Jacob Plachta: 2017-01-30 03:22:39

You need to select 0 or more subarrays, such that the sum of values in all of them is maximized. The number of elements in each subarray must be prime, and no two subarrays may be adjacent to one another.

vb: 2017-01-26 19:21:36

The problem statement in not clear. Kindly provide more explanation.

abdou_93: 2017-01-25 15:56:48

i think the problem not clear , please more explanation

Vipul Srivastava: 2017-01-24 17:46:02

No because 3+7=10 that is 10 consecutive numbers are selected and 10 is not a prime number.


Added by:Jamil Siam
Date:2017-01-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU