#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class key, class cmp = std::less<key>>
using op_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef thunder
#include "bug.h"
#else
#define bug(...) 
#endif

#define ll long long
#define lld double
#define all(x) x.begin(), x.end()
#define iceil(n, x) (((n) + (x) - 1) / (x))

const ll INF=2e18;
const ll mod=1000000007;
const ll maxn=1e5+5;

ll n;
vector<ll> a;
ll dp[maxn][4];
ll vis[maxn][4];

ll dfs(ll idx,ll cnt){
    if(idx>=n){
        if(cnt!=3) return -INF;
        return 0;
    }
    ll &ans=dp[idx][cnt];
    if(vis[idx][cnt]) return ans;
    vis[idx][cnt]=1;
    ans=0;
    ans=dfs(idx+1,cnt);
    if(cnt<3){
        if(cnt==0){
            ans=max(ans,dfs(idx+1,cnt+1)+(a[idx]+idx+1));
        }else if(cnt==1){
            ans=max(ans,dfs(idx+1,cnt+1)+a[idx]);
        }else if(cnt==2){
            ans=max(ans,dfs(idx+1,cnt+1)+a[idx]-(idx+1));
        }
    }
    return ans;
}

void solve(){
    cin>>n;
    a.resize(n);
    for(auto &i:a)  cin>>i;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<4;j++){
            dp[i][j]=-1;
            vis[i][j]=0;
        }
    }
    cout<<dfs(0,0)<<'\n';
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++){
        solve();
    }
    return 0;
}