#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define bp __builtin_popcountll
#define mp make_pair
#define x first
#define y second
#define Time (double)clock()/CLOCKS_PER_SEC
#define munq(a) sort(all(a)); a.resize(unique(all(a))-a.begin())
#define sz(a) ((int)a.size())
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
mt19937 rnd;
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#define lob(a,x) lower_bound(all(a),x)
#define upb(a,x) upper_bound(all(a),x)
int sz;
const int maxn=(1<<17);
const int inf=1e9;
int a[maxn];int rr[maxn];int ll[maxn];int rr2[maxn];int ll2[maxn];
int t[4*maxn];int t2[4*maxn];
void to(int node,int tl,int tr,int pos,int val)
{
    if(tr-tl==1)
    {
        t[node]=val;
        return;
    }
    int tm=(tl+tr)/2;
    if(pos<tm) {to(2*node+1,tl,tm,pos,val);} else {to(2*node+2,tm,tr,pos,val);}
    t[node]=min(t[2*node+1],t[2*node+2]);
}
int get(int node,int tl,int tr,int l,int r)
{
    if(tl>=r || tr<=l) return inf;
    if(tl>=l && tr<=r) {return t[node];}
    int tm=(tl+tr)/2;
    return min(get(2*node+1,tl,tm,l,r),get(2*node+2,tm,tr,l,r));
}
void to2(int node,int tl,int tr,int pos,int val)
{
    if(tr-tl==1)
    {
        t2[node]=val;
        return;
    }
    int tm=(tl+tr)/2;
    if(pos<tm) {to2(2*node+1,tl,tm,pos,val);} else {to2(2*node+2,tm,tr,pos,val);}
    t2[node]=min(t2[2*node+1],t2[2*node+2]);
}
int get2(int node,int tl,int tr,int l,int r)
{
    if(tl>=r || tr<=l) return inf;
    if(tl>=l && tr<=r) {return t2[node];}
    int tm=(tl+tr)/2;
    return min(get2(2*node+1,tl,tm,l,r),get2(2*node+2,tm,tr,l,r));
}
vector<pair<int,int> > rec;
void go(int l,int r)
{
    int m=(l+r)/2;
    if(r-l<4) return;
    if(r-l!=1) {go(l,m);go(m,r);}
    {
    for(int i=m;i<r;++i)
    {
        to(0,0,sz,a[i],i);
    }
    rec.clear();
    for(int i=m-1;i>=l;--i)
    {
        int pos=upper_bound(all(rec),make_pair(a[i],i))-rec.begin();
        if(pos!=rec.size())
        {
            int three=i;
            int four=rec[pos].second;
            int valone=get2(0,0,sz,three,four);
            if(valone>=a[three]) {continue;}
            int two=get(0,0,sz,valone,a[three]);
            //if(three==0 && two==2) {debug(a[0],a[1],a[2],a[3]);debug(valone);}
            rr[three]=min(rr[three],two-1);
        }
        if(rec.empty() || a[i]>=rec.back().first) {rec.app({a[i],i});}
    }
    for(int i=m;i<r;++i)
    {
        to(0,0,sz,a[i],inf);
    }
    }
    {
        vector<pair<int,int> > zxc1;
        int val=inf;
        for(int i=m-1;i>=l;--i)
        {
        zxc1.app({i,val});
        val=min(val,a[i]);
        }
        vector<pair<int,int> > zxc2;
        val=(-inf);
        for(int i=m;i<r;++i)
        {
            zxc2.app({val,i});
            val=max(val,a[i]);
        }
        sort(all(zxc1),[&](pair<int,int> i1,pair<int,int> j1) {return a[i1.first]>a[j1.first];});
        sort(all(zxc2));reverse(all(zxc2));
        int cur=0;
        //for(int i=0;i<4*sz;++i) assert(t[i]==inf);
        for(auto h:zxc1)
        {
            auto [i,mi]=h;
            if(mi>=a[i]) {continue;}
            while(cur<zxc2.size() && zxc2[cur].first>a[i])
            {
                int j=zxc2[cur].second;
                if(zxc2[cur].first<=a[j]) {++cur;continue;}
                //debug(a[j],j,zxc2[cur].first);
                to(0,0,sz,a[j],j);
                ++cur;
            }
            /*if(i==0 && get(0,0,sz,mi,a[i])==3)
            {
                debug(a[0],a[1],a[2],a[3],i,mi,m);
            }*/
            rr[i]=min(rr[i],get(0,0,sz,mi,a[i])-1);
        }
        for(int i=m;i<r;++i)
        {
        to(0,0,sz,a[i],inf);
        }
    }

}
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    int te;cin>>te;
    while(te--) {
    int n;cin>>n;int n1=n;
    for(int i=0;i<n;++i) {cin>>a[i];--a[i];}
    while(__builtin_popcount(n)!=1)
    {
        a[n]=n;++n;
    }
    sz=n;
    fill(t,t+4*sz,inf);fill(t2,t2+4*sz,inf);
    for(int i=0;i<n;++i) {rr[i]=n-1;ll[i]=0;}
    {
    for(int i=0;i<n;++i) {to2(0,0,sz,i,a[i]);}
    go(0,n);
    }
    for(int i=0;i<n;++i) {a[i]=n-1-a[i];}
    {
    for(int i=0;i<n;++i) {to2(0,0,sz,i,a[i]);}
    go(0,n);
    }
    //debug(rr[0]);
    copy(rr,rr+sz,rr2);fill(rr,rr+sz,n-1);
    copy(ll,ll+sz,ll2);fill(ll,ll+sz,0);
    reverse(a,a+n);
    for(int i=0;i<n;++i) {rr[i]=n-1;ll[i]=0;}
    {
    for(int i=0;i<n;++i) {to2(0,0,sz,i,a[i]);}
    go(0,n);
    }
    for(int i=0;i<n;++i) {a[i]=n-1-a[i];}
    {
    for(int i=0;i<n;++i) {to2(0,0,sz,i,a[i]);}
    go(0,n);
    }
    reverse(a,a+n);
    //for(int i=0;i<n;++i) {debug(i,ll[i],rr[i]);}
    for(int i=0;i<n;++i)
    {
        ll2[i]=max(ll2[i],n-1-rr[n-1-i]);
        rr2[i]=min(rr2[i],n-1-ll[n-1-i]);
    }
    copy(ll2,ll2+sz,ll);copy(rr2,rr2+sz,rr);
    for(int i=0;i<n;++i)
    {
        if(ll[i])
        {
            rr[ll[i]-1]=min(rr[ll[i]-1],i-1);
        }
    }
    for(int i=n-1;i>=1;--i)
    {
        rr[i-1]=min(rr[i-1],rr[i]);
    }
    //for(int i=0;i<n;++i) {debug(i,ll[i],rr[i]);}
    int dp[n+1]={0};fill(dp+1,dp+n+1,inf);dp[0]=0;
    for(int i=0;i<n;++i)
    {
        dp[rr[i]+1]=min(dp[rr[i]+1],dp[i]+1);
    }
    int res=0;
    for(int i=n1;i<=n;++i)
    {
        res=max(res,n1-dp[i]);
    }
    cout<<res<<'\n';
    }
    return 0;
}

/*
1
5
1 4 2 5 3
*/