Maximum Non-Adjacent Subsequence Sum

Given an array of integers, determine the maximum sum of a subsequence without choosing adjacent elements in the original array.

Input:

The first line consists of an integer 'T', the number of test cases.
For each test case, the first line contains an integer 'N', the number of elements in the array.
Followed by a line of 'N' space-separated integers, representing the array elements.

Output:

For each test case, output the maximum sum of non-adjacent elements, each result on a new line.

Example:

Input:

2
4
3 2 7 10
3
3 2 5

Output:

13
8

Explanation:

In the first test case, selecting 3 and 10 gives a sum of 13; not selecting adjacent 2. In the second test case, selecting 3 and 5 results in the maximum sum of 8.

Constraints:

• 1 <= T <= 500
• 1 <= N <= 1000
• 0 <= ARR[i] <= 10^5
• Time Limit: 1 sec.