Sammy the squirrel is gathering acorns for the winter. He finds a long wooden fence with N consecutive posts. Someone has left a random number of acorns on top of each post!
Sammy wants to collect as many acorns as he can. However, a large dog is sleeping right next to the fence. If Sammy takes acorns from two adjacent (side-by-side) fence posts, he will make too much noise and wake up the dog, who will chase him away.
Write a program to help Sammy figure out the maximum total number of acorns he can safely collect without waking the sleeping dog.
The first line contains a single integer T, representing the number of test cases.
For each test case:
The first line contains an integer N, representing the total number of fence posts.
The second line contains N space-separated integers, representing the number of acorns on each post, from left to right.
For each test case, print a single integer on a new line representing the maximum number of acorns Sammy can collect.
1 ≤ T ≤ 10
1 ≤ N ≤ 100000
0 ≤ number of acorns on a post ≤ 10000
The sum of N over all test cases will not exceed 500000.
| Example Input | Example Output |
|---|---|
2 4 3 2 7 10 5 2 7 9 3 1 |
13 12 |
Test Case 1: Sammy should take the acorns from post 1 (3 acorns) and post 4 (10 acorns). Total = 3 + 10 = 13 acorns. (He skips posts 2 and 3).
Test Case 2: Sammy should take the acorns from post 1 (2 acorns), post 3 (9 acorns), and post 5 (1 acorn). Total = 2 + 9 + 1 = 12 acorns.