#include <bits/stdc++.h>
using namespace std;
long long int mod = 1000000007;
long long int hmaxii = 100000000;
vector<long long int> storage;
long long int arr[5000][5000];
long long int upMax = 0, downMin = 0;
long long int ans = 0;
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int power(long long int a, long long int b) {
  if (b == 0) {
    return 1;
  }
  long long int temp = power(a, b / 2);
  temp = temp * temp;
  if (b % 2 == 1) {
    temp *= a;
  }
  return temp;
}
void solution() {
  long long int n;
  cin >> n;
  long long int arr[n];
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  if (n == 1) {
    cout << arr[0] << endl;
    return;
  }
  long long int sum[n][2];
  if (n % 2 == 1) {
    sum[n - 1][0] = arr[n - 1], sum[n - 1][1] = 0;
    sum[n - 2][0] = arr[n - 1], sum[n - 2][1] = arr[n - 2];
  } else {
    sum[n - 1][0] = 0, sum[n - 1][1] = arr[n - 1];
    sum[n - 2][0] = arr[n - 2], sum[n - 2][1] = arr[n - 1];
  }
  for (int i = n - 3; i >= 0; i--) {
    if (i % 2 == 0) {
      sum[i][0] = sum[i + 1][0] + arr[i];
      sum[i][1] = sum[i + 1][1];
    } else {
      sum[i][0] = sum[i + 1][0];
      sum[i][1] = sum[i + 1][1] + arr[i];
    }
  }
  long long int maxi[n];
  maxi[n - 1] = 0;
  if (n % 2 == 1) {
    maxi[n - 2] = arr[n - 2];
  } else {
    maxi[n - 2] = arr[n - 1];
  }
  for (int i = n - 3; i >= 0; i--) {
    maxi[i] = max(maxi[i + 2], sum[i + 2][0]);
    if (i % 2 == 0) {
      maxi[i] += arr[i + 1];
    } else {
      maxi[i] += arr[i];
    }
  }
  long long int ans = 0;
  long long int add = 0;
  for (int i = 0; i < n - 1; i++) {
    if (i % 2 == 0) {
      add += arr[i];
    }
    ans = max(ans, add + maxi[i + 1]);
  }
  if (n % 2 == 1) {
    add += arr[n - 1];
  }
  ans = max(ans, add);
  cout << max(ans, maxi[0]) << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int times;
  cin >> times;
  for (long long int i = 0; i < times; i++) {
    solution();
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

You are given an array a consisting of n integers. Indices of the array start from zero (i. e. the first element is a_0, the second one is a_1, and so on).

You can reverse at most one subarray (continuous subsegment) of this array. Recall that the subarray of a with borders l and r is a[l; r] = a_l, a_{l + 1}, ..., a_{r}.

Your task is to reverse such a subarray that the sum of elements on even positions of the resulting array is maximized (i. e. the sum of elements a_0, a_2, ..., a_{2k} for integer k = ⌊(n-1)/(2)⌋ should be maximum possible).

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of a. The second line of the test case contains n integers a_0, a_1, ..., a_{n-1} (1 ≤ a_i ≤ 10^9), where a_i is the i-th element of a.

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer on the separate line — the maximum possible sum of elements on even positions after reversing at most one subarray (continuous subsegment) of a.

Example

Input


4
8
1 7 3 4 7 6 2 9
5
1 2 1 2 1
10
7 8 4 5 7 6 8 9 7 3
4
3 1 2 1


Output


26
5
37
5

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int mod = 1000000007;
long long int hmaxii = 100000000;
vector<long long int> storage;
long long int arr[5000][5000];
long long int upMax = 0, downMin = 0;
long long int ans = 0;
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int power(long long int a, long long int b) {
  if (b == 0) {
    return 1;
  }
  long long int temp = power(a, b / 2);
  temp = temp * temp;
  if (b % 2 == 1) {
    temp *= a;
  }
  return temp;
}
void solution() {
  long long int n;
  cin >> n;
  long long int arr[n];
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  if (n == 1) {
    cout << arr[0] << endl;
    return;
  }
  long long int sum[n][2];
  if (n % 2 == 1) {
    sum[n - 1][0] = arr[n - 1], sum[n - 1][1] = 0;
    sum[n - 2][0] = arr[n - 1], sum[n - 2][1] = arr[n - 2];
  } else {
    sum[n - 1][0] = 0, sum[n - 1][1] = arr[n - 1];
    sum[n - 2][0] = arr[n - 2], sum[n - 2][1] = arr[n - 1];
  }
  for (int i = n - 3; i >= 0; i--) {
    if (i % 2 == 0) {
      sum[i][0] = sum[i + 1][0] + arr[i];
      sum[i][1] = sum[i + 1][1];
    } else {
      sum[i][0] = sum[i + 1][0];
      sum[i][1] = sum[i + 1][1] + arr[i];
    }
  }
  long long int maxi[n];
  maxi[n - 1] = 0;
  if (n % 2 == 1) {
    maxi[n - 2] = arr[n - 2];
  } else {
    maxi[n - 2] = arr[n - 1];
  }
  for (int i = n - 3; i >= 0; i--) {
    maxi[i] = max(maxi[i + 2], sum[i + 2][0]);
    if (i % 2 == 0) {
      maxi[i] += arr[i + 1];
    } else {
      maxi[i] += arr[i];
    }
  }
  long long int ans = 0;
  long long int add = 0;
  for (int i = 0; i < n - 1; i++) {
    if (i % 2 == 0) {
      add += arr[i];
    }
    ans = max(ans, add + maxi[i + 1]);
  }
  if (n % 2 == 1) {
    add += arr[n - 1];
  }
  ans = max(ans, add);
  cout << max(ans, maxi[0]) << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int times;
  cin >> times;
  for (long long int i = 0; i < times; i++) {
    solution();
  }
  return 0;
}

```