/*
TASK:seq
LANG:C++
*/
#include<iostream>
using namespace std;
class qw
{
      public:
             long long a,pos;
};
qw A[100005];
int f(qw a,qw b)
{
    if(a.a==b.a)return a.pos<b.pos;
    return a.a<b.a;
             
}
int solve()
{
     long long m,i;
     cin>>m;
     for(i=0;i<m;i++)
     {
                     cin>>A[i].a;
                     A[i].pos=i;
                     
     }
     sort(A,A+m,f);
     int l=0;
     for(i=1;i<m;i++)
     {
                     if(A[i].a<A[i-1].a)l++;
         if(l>1)return 0;
     }
         if(l>1)return 0;
         return 1;
     
}
int main()
{
int k;
cin>>k;
int i;
for(i=0;i<k;i++)
  cout<<solve();
 cout<<'\n';
 return 0;
}
