//HGOI zzk
#include<bits/stdc++.h>
using namespace std;
#define N 1000009
const int LEN=1<<21;
char BUF[LEN],PUF[LEN],*Pin=BUF,*Pout=PUF,*Pout_last=PUF+LEN-1,*Pin_last=BUF;
inline char Getchar(){return Pin==Pin_last&&(Pin_last=(Pin=BUF)+fread(BUF,1,LEN,stdin),Pin==Pin_last)?EOF:*Pin++;}
inline void Putchar(const char x){if(Pout==Pout_last)fwrite(PUF,1,Pout-PUF,stdout),Pout=PUF;*Pout++=x;}
inline int read(){int res=0,f=1;char ch=' ';while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=Getchar();}while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-48,ch=Getchar();return res*f;}
struct node
{
	int x,y;
}h1[N],h2[N];
inline bool cmp3(node a,node b){if(a.x==b.x) return a.y<b.y;return a.x<b.x;}
inline node cmp1(node a,node b){if(a.x==b.x) return a.y<b.y?b:a;return a.x<b.x?b:a;}
inline node cmp2(node a,node b){if(a.x==b.x) return a.y>b.y?b:a;return a.x>b.x?b:a;}
int flag[N],opt[N],vis[N],cnt,l1,r1,l2,r2;
inline void dfs(int i,int step)
{
	if(r2-l2+1+r1-l1+1==1) return;
	node maxx,minn;
	if(l1>r1)  maxx=h2[l2],minn=h2[r2],l2++,r2--;
	else if(l2>r2) maxx=h1[r1],minn=h1[l1],l1++,r1--;
	else 
	{
		maxx=cmp1(h1[r1],h2[l2]);
		minn=cmp2(h1[l1],h2[r2]);
		if(maxx.y==h1[r1].y) r1--;else l2++;
		if(minn.y==h1[l1].y) l1++;else r2--;
	}
//	printf("%d %d %d\n",step,minn.y,maxx.y);
	h2[++r2]=(node){maxx.x-minn.x,maxx.y};
	int j=r2;
	while(l2<j && cmp3(h2[j-1],h2[j])) swap(h2[j-1],h2[j]),j--;  
	dfs(i,step+1);
	if(!flag[step+1] || !vis[maxx.y]) 
	{
		flag[step]=1;
		opt[++cnt]=minn.y;
		vis[minn.y]=1;
	}
	else
	{
		for(int i=1;i<=cnt;i++) vis[opt[i]]=0;
		cnt=0;
	}
}
int a[N];
int main()
{
//	freopen("snakes.in","r",stdin);
//	freopen("snakes.out","w",stdout);
	int T=read(),x,y,nn;
	for(int i=0;i<T;i++)
	{
		memset(flag,0,sizeof(flag));
		int n=read();
		if(!i) 
		{
			nn=n;
			for(int j=1;j<=n;j++) a[j]=read();
		}
		else for(int j=1;j<=n;j++) x=read(),y=read(),a[x]=y;
		for(int j=1;j<=nn;j++) h1[j]=(node){a[j],j};
		cnt=0,l1=1,r1=nn,l2=1,r2=0,dfs(i,0);
		for(int j=0;j<=nn-1;j++) 
			if(!flag[j])
			{
				printf("%d\n",nn-j);
				break;
			}
	}
	return 0;
}