#include<bits/stdc++.h>
#define int long long
#define f(x,y) (x==y?x:0)
using namespace std;
const int N=1e6+5;
int n,a[N],dp[N];
int maxn[N<<2],tag[N<<2];
void pushup(int p){
maxn[p]=max(maxn[p<<1],maxn[p<<1|1]);
}
void setv(int p,int val){
tag[p]+=val;maxn[p]+=val;
}
void pushdown(int p){
if(tag[p]){
setv(p<<1,tag[p]);
setv(p<<1|1,tag[p]);
tag[p]=0;
}
}
void change1(int p,int l,int r,int k,int v){
if(l==r){
maxn[p]+=v;
return;
}int mid=l+r>>1;pushdown(p);
if(k<=mid)change1(p<<1,l,mid,k,v);
else change1(p<<1|1,mid+1,r,k,v);
pushup(p);
}
void change2(int p,int l,int r,int k,int v){
if(l==r){
maxn[p]=max(maxn[p],v);
return;
}int mid=l+r>>1;pushdown(p);
if(k<=mid)change2(p<<1,l,mid,k,v);
else change2(p<<1|1,mid+1,r,k,v);
pushup(p);
}
void read(int&x){
int t=1;x=0;char c=getchar();if(c=='-')t=-1;
while(c<'0'||c>'9'){c=getchar();if(c=='-')t=-1;}
while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
x*=t;
}
int solve(){
memset(maxn,-0x3f,sizeof(maxn));
memset(dp,-0x3f,sizeof(dp));
read(n);
for(int i=1;i<=n;i++)read(a[i]);
change2(1,0,N-5,0,0);
for(int i=1;i<=n;i++){
change1(1,0,N-5,a[i],a[i]);
dp[i]=max(dp[i],maxn[1]);
change1(1,0,N-5,a[i],-a[i]);
setv(1,f(a[i],a[i-1]));
change2(1,0,N-5,a[i-1],dp[i]);
}printf("%lld\n",maxn[1]);
return 0;
}
signed main(){
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
int t;scanf("%d",&t);
while(t--)solve();
return 0;
}