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 1^st, 2^nd element then 4^th, 5^th, 6^th element then 8^th, 9^th elements.

Another way can be to select 1^st and 2^nd 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