Maximum Fun Value

Kevin has a collection of toys, with each toy having a specific fun value. He wants to maximize the total fun by selecting a subset of these toys, with the caveat that no two selected toys have consecutive indices. In other words, if Kevin chooses the toy at index \(i\), he cannot choose the toy at index \(i+1\). Your task is to help Kevin determine the maximum total fun value he can achieve for each scenario.

Dynamic Programming Tip: Use the recurrence relation \(dp[i] = \max(dp[i-1], dp[i-2] + fun[i])\), along with proper initial conditions, to solve each test case efficiently.

For instance, for the fun values [3, 2, 7, 10, 12], the optimal selection is to pick the toys with fun values 3, 7, and 12, which sum to 22.

inputFormat

The input begins with an integer \(T\) denoting the number of test cases. Each test case is described as follows:

• The first line contains an integer \(n\), the number of toys.
• The second line contains \(n\) space-separated integers representing the fun values of the toys.

Note: If \(n = 0\), the corresponding maximum fun value is 0.

outputFormat

For each test case, print a single line containing the maximum total fun value that can be attained without selecting two consecutive toys.

## sample

3
5
3 2 7 10 12
4
100 1 100 1
3
5 5 10

22
200
15

</p>