Champa Max Gems

You are given T test cases. For each test case, you are provided an integer N followed by N integers that represent the values of gems arranged in a line. Your task is to select a subset of these gems such that no two chosen gems are adjacent, and the sum of their values is maximized.

Formally, given a sequence of gem values \(A_1, A_2, \ldots, A_N\), find the maximum possible sum \(\sum A_{i}\) where no two indices i and i+1 are both selected. This problem can be solved effectively using dynamic programming.

inputFormat

The first line of input contains an integer T, the number of test cases. For each test case, the first line contains an integer N indicating the number of gems. The next line contains N space-separated integers representing the gem values.

outputFormat

For each test case, output a single line containing the maximum sum of non-adjacent gem values.

2
4
3 2 5 10
5
2 10 3 5 7

13
17