Turtle Fed Optimal Food

You are given a turtle that is fed over N days. On each day, the turtle consumes a certain amount of food. However, the turtle has a peculiar eating habit: it does not eat on two consecutive days. Your task is to determine the maximum sum of food quantities that the turtle can consume without eating on consecutive days.

You can formulate the problem using the following recurrence relation in \(\LaTeX\):

[ \text{dp}[i] = \max(\text{dp}[i-1],,\text{dp}[i-2] + \text{food}[i]) ]

where \(\text{dp}[i]\) represents the maximum sum possible up to day \(i\), and \(\text{food}[i]\) is the food quantity on day \(i\). The answer for each test case will be \(\text{dp}[N-1]\) (assuming 0-indexing).

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer T, the number of test cases.
• For each test case:
• The first line contains an integer N, the number of days.
• The second line contains N space-separated integers representing the food quantities on each day.

outputFormat

For each test case, output the maximum sum of food quantities that the turtle can consume under the constraint of not eating on consecutive days. Each result should be printed on a separate line to standard output (stdout).

## sample

1
4
3 2 5 10

13

</p>