Maximum Sum of Non-Adjacent Subsequence

Given an array of integers, your task is to find the maximum possible sum from a subsequence such that no two elements in the subsequence are adjacent in the original array.

You can solve this problem using dynamic programming. The recurrence relation for the problem is given by:

\(dp[i] = \max(dp[i-1], dp[i-2] + a_i)\)

where \(dp[i]\) is the maximum sum achievable using the first \(i+1\) elements of the array.

The input consists of multiple test cases. For each test case, you are given an integer \(N\) representing the number of elements in the array, followed by \(N\) integers.

inputFormat

The first line of the input contains a single integer \(T\) denoting the number of test cases. Each test case consists of two lines:

• The first line contains a single integer \(N\) representing the size of the array.
• The second line contains \(N\) space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single line containing the maximum sum of a subsequence where no two elements are adjacent.

## sample

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

22
6

</p>