#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
void debug_(const auto&...a){
	((std::cerr<<a<<' '),...)<<'\n';
}
#define debug(a...) debug_(__LINE__,":",#a,"=",a)
using ll=long long;
#define int ll
using i128=__int128;
template<typename T>using V=std::vector<T>;
using vi=V<int>;
using pii=std::pair<int,int>;
using std::cin,std::cerr,std::cout;
#define all(c) std::begin(c),std::end(c)
#define eb emplace_back
#define pb push_back
constexpr ll M=ll(1e18)+9;
pii&operator+=(pii&a,pii b){
	if(a.first<b.first)std::swap(a,b);
	if(a.first==b.first)(a.second+=b.second)%=M;
	return a;
}
signed main(){
	// sieve();
	// for(auto&x:prime)cerr<<x<<' ';
	cin.tie(0)->sync_with_stdio(0);
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		vi p(n+2);
		// vi fi=p,fd=p;
		// vi fwi=p,fwd=p;
		for(int i=1;i<=n;++i)cin>>p[i];
		auto solve=[&](){//LIS by default
			V<pii>fw(n+2),f(n+2);
			auto add=[&](int i,pii x){
				for(++i;i<ssize(fw);i+=i&-i)fw[i]+=x;
			};
			auto sum=[&](int i){
				pii x(-1,0);
				for(++i;i;i-=i&-i)x+=fw[i];
				return x;
			};
			add(0,pii(0,1));
			for(int i=1;i<=n;++i){
				f[i]=sum(p[i]);
				f[i].first++;
				add(p[i],f[i]);
			}
			f.back()=sum(n);
			return f;
		};
		auto prei=solve();
		for(auto&x:p)x=n-x+1;
		auto pred=solve();
		reverse(all(p));
		auto sufi=solve();
		for(auto&x:p)x=n-x+1;
		auto sufd=solve();
		auto[ansi,wi]=prei.back();
		auto[ansd,wd]=pred.back();
		i128 tot=wi;
		(tot*=wd)%=M;
		for(int i=1;i<=n;++i)if(prei[i].first+sufi[n-i+1].first-1==ansi&&pred[i].first+sufd[n-i+1].first-1==ansd){
			tot=(tot-prei[i].second*i128(pred[i].second)%M*sufi[n-i+1].second%M*sufd[n-i+1].second)%M;
		}
		printf("%lld\n",ll(ansi+ansd-(!tot)));
	}
}