for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
dp = [[0, 0, 0] for _ in range(n+1)]
for i in range(n):
dp[i+1][0] = max(dp[i+1][0], dp[i][0] + (0 if i & 1 else a[i]))
if i+2 <= n:
dp[i+2][1] = max(dp[i+2][1], max(dp[i][0], dp[i][1]) + (a[i] if i&1 else a[i+1]))
dp[i+1][2] = max(dp[i+1][2], max(dp[i][0], dp[i][1], dp[i][2]) + (0 if i&1 else a[i]))
print(max(dp[n][0], dp[n][1], dp[n][2]))
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define nl cout<<'\n'
#define ll long long
#define isodd(x) if(x&1)
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll max_subarray_sum(vector<ll> &v)
{
ll max_so_far=LLONG_MIN,max_ending_here=0;
for(auto &va:v)
{
max_ending_here+=va;
if(max_ending_here>max_so_far)
max_so_far=max_ending_here;
if(max_ending_here<0)
max_ending_here=0;
}
return max_so_far;
}
int main()
{
fast
int t,n;
cin>>t;
while(t--)
{
cin>>n;
ll a[n],ans=0,sum=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(i%2==0) sum+=a[i];
}
vector<ll> v;
for(int i=0;i<n-1;i+=2)
v.push_back(a[i+1]-a[i]);
ans=max(sum,sum+max_subarray_sum(v));
v.clear();
for(int i=1;i<n-1;i+=2)
v.push_back(a[i]-a[i+1]);
ans=max(ans,sum+max_subarray_sum(v));
cout<<ans<<endl;
}
}1478A - Nezzar and Colorful Balls | 1581B - Diameter of Graph |
404A - Valera and X | 908A - New Year and Counting Cards |
146A - Lucky Ticket | 1594C - Make Them Equal |
1676A - Lucky | 1700B - Palindromic Numbers |
702C - Cellular Network | 1672C - Unequal Array |
1706C - Qpwoeirut And The City | 1697A - Parkway Walk |
1505B - DMCA | 478B - Random Teams |
1705C - Mark and His Unfinished Essay | 1401C - Mere Array |
1613B - Absent Remainder | 1536B - Prinzessin der Verurteilung |
1699B - Almost Ternary Matrix | 1545A - AquaMoon and Strange Sort |
538B - Quasi Binary | 424A - Squats |
1703A - YES or YES | 494A - Treasure |
48B - Land Lot | 835A - Key races |
1622C - Set or Decrease | 1682A - Palindromic Indices |
903C - Boxes Packing | 887A - Div 64 |