#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll p[1000001],a[1000001];
ll f[1000001];

int main(){
    // freopen("2.in","r",stdin);
    // freopen("2.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--){
        ll n;
        scanf("%lld",&n);
        for(ll i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(a[i]==0){
                a[0]=i;
            }
        }
        a[0]--;
        for(ll i=1;i<=n;i++){
            p[i]=a[++a[0]];
            a[0]%=n;
        }
        stack<pair<ll,ll>> s;
        s.push({1,0});
        memset(a,0,sizeof(a));
        // for(int i=2;i<=n;i++){
        //     for(int j=i-1;j>=1;j--){
        //         if(p[j]<p[i]){
        //             a[i]=j;
        //             break;
        //         }
        //     }
        // }
        for(ll i=2;i<=n;i++){
            while(!s.empty()&&s.top().second>p[i]){
                s.pop();
            }
            a[i]=s.top().first;
            s.push({i,p[i]});
        }
        memset(f,0,sizeof(f));
        for(ll i=1;i<=n;i++){
            f[i]=f[a[i]]+p[i]*(i-a[i]);
        }
        ll ans=0;
        for(ll i=1;i<=n;i++){
            // cout<<f[i]<<" ";
            ans=max(ans,f[i]);
        }
        printf("%lld\n",ans+n);
    }
    // cout<<cnt;
	return 0;
}